제출 #592405

#제출 시각아이디문제언어결과실행 시간메모리
592405ogibogi2004카니발 티켓 (IOI20_tickets)C++14
0 / 100
973 ms2097152 KiB
#include "tickets.h" #include <vector> #include<bits/stdc++.h> using namespace std; long long find_maximum(int k, vector<vector<int>> x) { //cout<<"?\n"; int n = x.size(); int m = x[0].size(); vector<vector<int>> answer; vector<int>smallest[n]; for(int i=0;i<n;i++) { smallest[i]=x[i]; sort(smallest[i].begin(),smallest[i].end()); } int use[n][m]; memset(use,-1,sizeof(use)); int dp[n][n*k]; int hist[n][n*k]; bool c[n][n*k]; memset(c,0,sizeof(c)); int sum=0; for(int j=0;j<k;j++)sum-=smallest[0][j]; dp[0][k]=sum;c[0][k]=1; hist[0][k]=k; for(int j=k-1;j>=0;j--) { sum+=smallest[0][j]; sum+=smallest[0][smallest[0].size()-(k-j)]; dp[0][j]=sum;c[0][j]=1; hist[0][j]=j; } //cout<<"eho1\n"; for(int i=1;i<n;i++) { sum=0; for(int j=0;j<k;j++)sum-=smallest[i][j]; for(int prv=0;prv+k<=n*k/2;prv++) { if(!c[i-1][prv])continue; if(c[i][prv+k]==0) { dp[i][prv+k]=dp[i-1][prv]+sum; c[i][prv+k]=1; hist[i][prv+k]=k; } else { if(dp[i-1][prv]+sum>dp[i][prv+k]) { dp[i][prv+k]=dp[i-1][prv]+sum; hist[i][prv+k]=k; } } } for(int j=k-1;j>=0;j--) { sum+=smallest[i][j]; sum+=smallest[i][smallest[i].size()-(k-j)]; for(int prv=0;prv+j<=n*k/2;prv++) { if(!c[i-1][prv])continue; if(c[i][prv+j]==0) { dp[i][prv+j]=dp[i-1][prv]+sum; hist[i][prv+j]=j; c[i][prv+j]=1; } else { if(dp[i-1][prv]+sum>dp[i][prv+j]) { dp[i][prv+j]=dp[i-1][prv]+sum; hist[i][prv+j]=j; } } } } } //cout<<"eho2\n"; int t=n*k/2; vector<int>small[n]; vector<int>large[n]; for(int j=n-1;j>=0;j--) { //cout<<j<<" "<<t<<endl; int cnts=hist[j][t]; //cout<<" "<<cnts<<endl; vector<pair<int,int> >smallest1; for(int i=0;i<m;i++) { smallest1.push_back({x[j][i],i}); } sort(smallest1.begin(),smallest1.end()); for(int i=0;i<cnts;i++) { small[j].push_back(smallest1[i].second); } for(int i=1;i<=k-cnts;i++) { large[j].push_back(smallest1[m-i].second); } t-=cnts; } //cout<<"eho3\n"; //cout<<dp[n-1][n*k/2]<<endl; for(int j=0;j<k;j++) { //cout<<j<<endl; vector<pair<int,int> >sizes; for(int i=0;i<n;i++) { sizes.push_back({small[i].size(),i}); } sort(sizes.rbegin(),sizes.rend()); for(int i=0;i<sizes.size();i++) { //cout<< " "<<i<<endl; if(i<n/2) { //cout<<" "<<small[sizes[i].second].size()<<endl; use[sizes[i].second][small[sizes[i].second].back()]=j; small[sizes[i].second].pop_back(); } else { use[sizes[i].second][large[sizes[i].second].back()]=j; large[sizes[i].second].pop_back(); } } } //cout<<"eho4\n"; for(int i=0;i<n;i++) { //cout<<i<<endl; vector<int>v; for(int j=0;j<m;j++) { v.push_back(use[i][j]); } answer.push_back(v); } allocate_tickets(answer); return dp[n-1][n*k/2]; } /* 2 3 2 0 2 5 1 1 3 */

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

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:118:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for(int i=0;i<sizes.size();i++)
      |                     ~^~~~~~~~~~~~~
#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...