제출 #751952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
751952		grogu	Council (JOI23_council)	C++14	100 / 100	1208 ms	100136 KiB

council

        #include "bits/stdc++.h"
        #define int long long
        using namespace std;
        int32_t main() {
          ios::sync_with_stdio(0);
          cin.tie(0);
          int n, m;
          cin >> n >> m;
          int a[n][m];
          int b[n];
          int s[m];
          for(int i=0; i<m; i++) s[i] = 0;
          for(int i=0; i<n; i++) {
            b[i] = 0;
            for(int j=0; j<m; j++) {
              cin >> a[i][j];
              s[j] += a[i][j];
              b[i] |= (a[i][j] << j);
            }
          }
          int cnt[(1<<m)];
          int ans[(1<<m)];
          for(int i=0; i<(1<<m); i++) cnt[i] = 0, ans[i] = -1;
          for(int i=0; i<n; i++) cnt[b[i]]++;
          pair<int,int> dp[(1<<m)][2];
          for(int i=0; i<(1<<m); i++) for(int j=0; j<2; j++) dp[i][j] = {1e9, -1};
          for(int i=0; i<n; i++) {
            if(dp[b[i]][0].first == 0) dp[b[i]][1] = {0, i};
            else dp[b[i]][0] = {0, i};
          }
          for(int i=0; i<m; i++) {
            for(int j=0; j<(1<<m); j++) {
              if(j & (1<<i)) {
                vector<pair<int,int> > w = {
                  dp[j^(1<<i)][0], dp[j^(1<<i)][1],
                  dp[j][0], dp[j][1]
                };
                sort(w.begin(),w.end());
                dp[j][0] = w[0];
                for(int k=1; k<4; k++) {
                  if(dp[j][0].second != w[k].second) {
                    dp[j][1] = w[k]; break;
                  }
                }
              }
            }
          }
          reverse(dp, dp+(1<<m));
          for(int j=m-1;j>=0;j--) {
            for(int i = 1;i<(1<<m);i++) {
              if(dp[i][1].first == 0) continue;
              if(i&(1<<j)) {
                int tar0=dp[i^(1<<j)][0].first+1, tar1=dp[i^(1<<j)][1].first+1;
                vector<pair<int,int> > w = {
                  {tar0,dp[i^(1<<j)][0].second},
                  {tar1,dp[i^(1<<j)][1].second},
                  dp[i][0],dp[i][1]
                };
                sort(w.begin(), w.end());
                dp[i][0] = w[0];
                for(int k=1; k<4; k++) {
                  if(dp[i][0].second != w[k].second) {
                    dp[i][1] = w[k]; break;
                  }
                }
              }
            }
          }
          for(int i=0; i<n; i++) {
            int bad = 0, base = 0;
            for(int j=0; j<m; j++) {
              int ss = s[j] - a[i][j];
              if(ss >= n/2) base++;
              if(ss == n/2) bad |= (1<<j);
            }
            int opt = dp[bad][0].first;
            if(dp[bad][0].second == i) opt = dp[bad][1].first;
            cout << base - opt << '\n';
          }
        }

컴파일 시 표준 에러 (stderr) 메시지

council.cpp: In function 'int32_t main()':
council.cpp:22:15: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   22 |           int ans[(1<<m)];
      |               ^~~

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 19 / 19
• Subtask 5: 15 / 15
• Subtask 6: 22 / 22
• Subtask 7: 22 / 22