제출 #592442

#제출 시각아이디문제언어결과실행 시간메모리
592442ogibogi2004카니발 티켓 (IOI20_tickets)C++14
27 / 100
609 ms145980 KiB
#include "tickets.h" #include <vector> #include<bits/stdc++.h> using namespace std; #define ll long long long long find_maximum(int k, vector<vector<int>> x1) { //cout<<"?\n"; vector<vector<ll> >x; for(int i=0;i<x1.size();i++) { vector<ll>row; for(int j=0;j<x1[i].size();j++)row.push_back(x1[i][j]); x.push_back(row); } ll n = x.size(); ll m = x[0].size(); vector<vector<int>> answer; vector<pair<ll,ll>>smallest[n]; int ptr1[n],ptr2[n]; for(ll i=0;i<n;i++) { for(ll j=0;j<m;j++)smallest[i].push_back({x[i][j],j}); sort(smallest[i].begin(),smallest[i].end()); ptr1[i]=0;ptr2[i]=smallest[i].size()-1; } ll ans=0; for(int i=0;i<n;i++) { answer.push_back({}); for(int j=0;j<m;j++)answer[i].push_back(-1); } for(int r=0;r<k;r++) { ll dp[n][n]; bool c[n][n]; memset(c,0,sizeof(c)); int hist[n][n]; for(int i=0;i<n;i++) { //cout<<r<<" "<<i<<endl; if(i==0) { c[0][0]=1; c[0][1]=1; hist[0][0]=0; hist[0][1]=1; dp[0][0]=smallest[0][ptr2[i]].first; dp[0][1]=-smallest[0][ptr1[i]].first; continue; } for(int j=n/2;j>=0;j--) { //plus if(c[i-1][j]) { if(c[i][j]) { if(dp[i-1][j]+smallest[i][ptr2[i]].first>dp[i][j]) { dp[i][j]=dp[i-1][j]+smallest[i][ptr2[i]].first; hist[i][j]=0; } } else { dp[i][j]=dp[i-1][j]+smallest[i][ptr2[i]].first; hist[i][j]=0; c[i][j]=1; } } //minus if(c[i-1][j-1]) { if(!c[i][j]) { dp[i][j]=dp[i-1][j-1]-smallest[i][ptr1[i]].first; hist[i][j]=1; c[i][j]=1; } else { if(dp[i-1][j-1]-smallest[i][ptr1[i]].first>dp[i][j]) { dp[i][j]=dp[i-1][j-1]-smallest[i][ptr1[i]].first; hist[i][j]=1; } } } //if(c[i][j])cout<<i<<" "<<j<<" : "<<dp[i][j]<<endl; } } //cout<<r<<" "<<dp[n-1][n/2]<<endl; ans+=dp[n-1][n/2]; int t=n/2; for(int i=n-1;i>=0;i--) { //cout<<i<<" "<<t<<endl; int f=hist[i][t]; //cout<<" "<<f<<endl; if(f==1) { answer[i][smallest[i][ptr1[i]].second]=r; ptr1[i]++; } else { answer[i][smallest[i][ptr2[i]].second]=r; ptr2[i]--; } t-=f; } //cout<<"alo\n"; } allocate_tickets(answer); return ans; } /* 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:9:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for(int i=0;i<x1.size();i++)
      |                 ~^~~~~~~~~~
tickets.cpp:12:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |         for(int j=0;j<x1[i].size();j++)row.push_back(x1[i][j]);
      |                     ~^~~~~~~~~~~~~
#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...