fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
  6.  
  7. #define rf if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
  8. #define rd ({int x = 0; int c = getchar(), n = 0; for(; !isdigit(c); c = getchar()) n = (c == '-'); for(; isdigit(c); c = getchar()) x = x * 10 + c - '0'; n ? -x : x;})
  9.  
  10. #define bit(i, mask) (((mask) >> (i)) & 1)
  11. #define on(i, mask) ((mask) | (1LL << (i)))
  12. #define off(i, mask) ((mask) & (~(1LL << (i))))
  13.  
  14. #define ll long long
  15. #define fi first
  16. #define se second
  17. #define pii pair<int, int>
  18. #define vii vector<int>
  19. #define all(a) (a).begin(), (a).end()
  20. #define len(x) ((int)(x).size())
  21. #define pb push_back
  22. #define endl '\n'
  23. #define TIME (1.0 * clock() / CLOCKS_PER_SEC)
  24.  
  25. #define name ""
  26.  
  27. template<typename T1, typename T2> bool mini(T1 &a, T2 b)
  28.     {if(a > b) a = b; else return 0; return 1;}
  29. template<typename T1, typename T2> bool maxi(T1 &a, T2 b)
  30.     {if(a < b) a = b; else return 0; return 1;}
  31.  
  32. const int mod = 1e9+7;
  33. const int inf = 1e9+9;
  34. const ll oo = 1e18l+7;
  35. const int M = 5e5+6;
  36. const int N = 2468;
  37. const int LOG = 31 - __builtin_clz(N);
  38.  
  39. int n, m, s[N][N];
  40.  
  41. struct Edge{
  42.     int v, flow, cap;
  43. };
  44.  
  45. struct Dinic{
  46.     int n, s, t, work[N], d[N];
  47.     vector<Edge> e;
  48.     vii a[N];
  49.     Dinic(int _n, int _s, int _t){
  50.         n = _n, s = _s, t = _t;
  51.     }
  52.  
  53.     void Add(int u, int v, int c){
  54.         e.pb({v, 0, c});
  55.         a[u].pb(e.size() - 1);
  56.         e.pb({u, 0, 0});
  57.         a[v].pb(e.size() - 1);
  58.     }
  59.  
  60.     bool bfs(){
  61.         for(int i = 1; i <= n; i++) d[i] = 0;
  62.         d[s] = 1;
  63.         queue<int> q;
  64.         q.push(s);
  65.         while(!q.empty()){
  66.             int k = q.front();
  67.             q.pop();
  68.             for(int u : a[k]){
  69.                 int v = e[u].v;
  70.                 if(e[u].cap > e[u].flow && d[v] == 0){
  71.                     d[v] = d[k] + 1;
  72.                     q.push(v);
  73.                 }
  74.             }
  75.         }
  76.         return d[t] > 0;
  77.     }
  78.  
  79.     int dfs(int u, int flow){
  80.         if(u == t) return flow;
  81.         for(int &z = work[u]; z < (int)a[u].size(); z++){
  82.             int i = a[u][z];
  83.             int v = e[i].v;
  84.             if(e[i].cap > e[i].flow && d[v] == d[u] + 1){
  85.                 int tmp = dfs(v, min(flow, e[i].cap - e[i].flow));
  86.                 if(tmp){
  87.                     e[i].flow += tmp;
  88.                     e[i ^ 1].flow -= tmp;
  89.                     return tmp;
  90.                 }
  91.             }
  92.         }
  93.         return 0;
  94.     }
  95.  
  96.     int getFlow(){
  97.         int res = 0;
  98.         while(bfs()){
  99.             for(int i = 1; i <= n; i++) work[i] = 0;
  100.             while(int delta = dfs(s, inf)) res += delta;
  101.         }
  102.         //for(int i = 0; i < e.size(); i += 2) cout << e[i].flow << endl;
  103.         return res;
  104.     }
  105. };
  106.  
  107. void in(){
  108.     cin >> n >> m;
  109.     for(int i = 1; i <= n; i++){
  110.         for(int j = 1; j <= m; j++) cin >> s[i][j];
  111.     }
  112. }
  113.  
  114. namespace subtask1{
  115.     int dp[15][1 << 12], trace[15][1 << 12], cost[15][1 << 12];
  116.  
  117.     void solve(){
  118.         for(int i = 1; i <= n; i++){
  119.             for(int mask = 0; mask < (1 << m); mask++){
  120.                 for(int j = 0; j < m; j++) if(bit(j, mask)) cost[i][mask] += s[i][j + 1];
  121.             }
  122.         }
  123.         memset(dp, -1, sizeof dp);
  124.         dp[0][0] = inf;
  125.         for(int mask = 0; mask < (1 << m); mask++){
  126.             for(int i = 0; i < n; i++){
  127.                 if(dp[i][mask] == -1) continue;
  128.                 int tmp = ((1 << m) - 1) ^ mask;
  129.                 for(int submask = tmp; submask > 0; submask = (submask - 1) & tmp){
  130.                     if(maxi(dp[i + 1][mask ^ submask], min(cost[i + 1][submask], dp[i][mask])))
  131.                         trace[i + 1][mask ^ submask] = submask;
  132.                 }
  133.             }
  134.         }
  135.         vii ans;
  136.         int mask = (1 << m) - 1;
  137.         while(n > 0){
  138.             ans.pb(trace[n][mask]);
  139.             mask ^= trace[n][mask];
  140.             n--;
  141.         }
  142.         reverse(all(ans));
  143.         for(int it : ans){
  144.             cout << __builtin_popcount(it) << " ";
  145.             for(int i = 1; i <= m; i++) if(bit(i - 1, it)) cout << i << " ";
  146.             cout << endl;
  147.         }
  148.     }
  149. }
  150.  
  151. namespace subtask2{
  152.     int dp[2][100005], trace[1234][100005];
  153.     // dp[i][j]: maxi 1, j la delta 1 va 2 => max = dp - j
  154.     // y tuong tu bai treasure (th tre)
  155.  
  156.     void solve(){
  157.         memset(dp[0], -0x3f, sizeof dp);
  158.         int w = 50000;
  159.         dp[0][w] = 0;
  160.         for(int i = 1; i <= m; i++){
  161.             int cur = i & 1, pre = cur ^ 1;
  162.             for(int j = -w; j <= w; j++) dp[cur][j + w] = -inf;
  163.             for(int j = -w; j <= w; j++){
  164.                 if(dp[pre][j + w] == -inf) continue;
  165.                 if(j + s[1][i] <= w && maxi(dp[cur][j + w + s[1][i]], dp[pre][j + w] + s[1][i]))
  166.                     trace[i][j + w + s[1][i]] = 1;
  167.                 if(j - s[2][i] >= -w && maxi(dp[cur][j + w - s[2][i]], dp[pre][j + w]))
  168.                     trace[i][j + w - s[2][i]] = 2;
  169.             }
  170.         }
  171.  
  172.         int val = 0, id = 0;
  173.         for(int i = -w; i <= w; i++){
  174.             if(dp[m & 1][i + w] == -inf) continue;
  175.             if(maxi(val, dp[m & 1][i + w] - (i > 0 ? i : 0))) id = i + w;
  176.         }
  177.  
  178.         vii va, vb;
  179.         while(m){
  180.             if(trace[m][id] == 1){
  181.                 va.pb(m);
  182.                 id -= s[1][m];
  183.             }
  184.             else{
  185.                 vb.pb(m);
  186.                 id += s[2][m];
  187.             }
  188.             m--;
  189.         }
  190.         reverse(all(va)); reverse(all(vb));
  191.         cout << len(va) << ' ';
  192.         for(int it : va) cout << it << ' ';
  193.         cout << endl;
  194.         cout << len(vb) << ' ';
  195.         for(int it : vb) cout << it << ' ';
  196.     }
  197. }
  198.  
  199. namespace subtask3{
  200.     int st, en, cnt, ng[N], gift[N];
  201.  
  202.     bool check(int x){
  203.         Dinic mxFlow(cnt, st, en);
  204.         for(int i = 1; i <= n; i++){
  205.             for(int j = 1; j <= m; j++) if(s[i][j] >= x) mxFlow.Add(ng[i], gift[j], 1);
  206.         }
  207.         for(int i = 1; i <= n; i++) mxFlow.Add(st, ng[i], 1);
  208.         for(int i = 1; i <= m; i++) mxFlow.Add(gift[i], en, 1);
  209.         return (mxFlow.getFlow() == n);
  210.     }
  211.  
  212.     void output(int x){
  213.         Dinic mxFlow(cnt, st, en);
  214.         for(int i = 1; i <= n; i++){
  215.             for(int j = 1; j <= m; j++) if(s[i][j] >= x) mxFlow.Add(ng[i], gift[j], 1);
  216.         }
  217.         for(int i = 1; i <= n; i++) mxFlow.Add(st, ng[i], 1);
  218.         for(int i = 1; i <= m; i++) mxFlow.Add(gift[i], en, 1);
  219.         mxFlow.getFlow();
  220.         for(int i = 1; i <= n; i++){
  221.             int u = ng[i];
  222.             for(auto it : mxFlow.a[u]){
  223.                 int v = mxFlow.e[it].v;
  224.                 if(mxFlow.e[it].flow == 1){
  225.                     cout << 1 << ' ' << v - n << endl;
  226.                     break;
  227.                 }
  228.             }
  229.         }
  230.     }
  231.  
  232.     void solve(){
  233.         for(int i = 1; i <= n; i++) ng[i] = ++cnt;
  234.         for(int i = 1; i <= m; i++) gift[i] = ++cnt;
  235.         st = ++cnt, en = ++cnt;
  236.         int l = 1, r = 1000, res = 1;
  237.         while(l <= r){
  238.             int mid = (l + r) >> 1;
  239.             if(check(mid)){
  240.                 res = mid;
  241.                 l = mid + 1;
  242.             }
  243.             else r = mid - 1;
  244.         }
  245.         output(res);
  246.     }
  247. }
  248.  
  249. void proc(){
  250.     if(n <= 12 && m <= 12){
  251.         subtask1::solve();
  252.         return;
  253.     }
  254.     if(n == 2){
  255.         subtask2::solve();
  256.         return;
  257.     }
  258.     subtask3::solve();
  259. }
  260.  
  261. int main(){
  262.     cin.tie(nullptr)->sync_with_stdio(false);
  263.  
  264.     rf
  265.  
  266.     int test = 1;
  267.     //cin >> test;
  268.  
  269.     while(test--){
  270.         in();
  271.         proc();
  272.     }
  273.  
  274.     cerr << "Time elapsed: " << TIME << "s" << endl;
  275.     return 0;
  276. }
  277.  
Success #stdin #stdout #stderr 0.01s 5824KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Time elapsed: 0.004955s
https://ideone.com/WGaBzu
language:
C++14 (gcc 8.3)
created:
1 hour ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!