제출 #576164

#제출 시각아이디문제언어결과실행 시간메모리
576164MadokaMagicaFan카니발 티켓 (IOI20_tickets)C++14
11 / 100
2 ms1492 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; using pi = pair<int,int>; #define all(v) v.begin(),v.end() #define sort(v) sort(all(v)) #define endl '\n' #define forn(i,n) for(int i = 0; i < n; ++i) #define forbe(i,b,e) for(int i = b; i < e; ++i) #define forr(i,n) for(int i = n-1; i >= 0; --i) #define sz(v) ((int)v.size()) #define pb push_back #define f first #define s second const int N = 1500; const int M = 1500; void allocate_tickets(vector<vi>s); ll subtask1(int k, vector<vi> &x) { int n = sz(x); int m = sz(x[0]); vector<vi> s(n); forn(i,n) s[i].assign(m,0); vi ans; forn(i,n) { ans.pb(x[i][0]); } sort(ans); ll rans = 0; forn(i,n) { if (i < (n>>1)) rans -= ans[i]; else rans += ans[i]; } forn(i,n) { s[i][0] = 0; } allocate_tickets(s); return rans; } ll subtask4(int k, vector<vi> &x) { int n = sz(x); int m = sz(x[0]); vector<vi> s(n); forn(i,n) s[i].assign(m,0); vector<pi> vals; vector<vector<pi>> sval(n); int topp[N]; int botp[N]; forn(i,n) { topp[i] = n-1; botp[i] = 0; forn(j,m) { sval[i].pb({x[i][j], j}); vals.pb({x[i][j],i * m + j}); } sort(sval[i]); } ll ans = 0; sort(vals); bitset<N*M> c; bitset<N*M> mid; int midval = vals[((n*m)>>1)].f; forn(i,n*m) { ans -= (ll)vals[i].f; if (vals[i].f == midval) mid[i] = 1; if (i < ((n*m)>>1)) continue; c[vals[i].s] = 1; ans += (ll)vals[i].f; ans += (ll)vals[i].f; } bitset<N> up; int cnt; forn(j, k) { forn(i,n) up[i] = 0; cnt = 0; forn(i,n) { if (cnt == (n>>1)) break; if (c[ i*m + sval[i][topp[i]].s ] == 0) continue; ++cnt; up[i]=1; } forn(i,n) { if (cnt == (n>>1)) break; if (up[i]) continue; if (mid[ i*m + sval[i][topp[i]].s ] == 0) continue; ++cnt; up[i]=1; } assert(cnt == (n>>1)); forn(i,n) { if (up[i]) { s[i][ sval[i][topp[i]].s ] = j; --topp[i]; } else { s[i][ sval[i][botp[i]].s ] = j; ++botp[i]; } } } allocate_tickets(s); return ans; } ll find_maximum(int k, vector<vi>x) { int n = sz(x); int m = sz(x[0]); if (m == 1) return subtask1(k,x); if (m == k) return subtask4(k,x); return 0; } #ifdef ONPC void allocate_tickets(vector<vi>s) { forn(i, sz(s)) { forn(j, sz(s[0])) { cout << s[i][j] << ' '; } cout << endl; } } void solve() { int n, m, k; cin >> n >> m >> k; vector<vi> x(n); forn(i,n) { x[i].assign(m,0); } forn(j,m) { forn(i,n) { cin >> x[i][j]; } } cout << find_maximum(k, x) << endl; } int main() { freopen("in", "r", stdin); // ios_base::sync_with_stdio(0);cin.tie(0); solve(); } #endif

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

tickets.cpp: In function 'll find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:136:9: warning: unused variable 'n' [-Wunused-variable]
  136 |     int n = sz(x);
      |         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...