Submission #1031286

#TimeUsernameProblemLanguageResultExecution timeMemory
1031286AndreyCoin Collecting (JOI19_ho_t4)C++14
37 / 100
1020 ms21212 KiB
#include<bits/stdc++.h> using namespace std; int haha[100001][2]; long long dp[3000][3000]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n,x,y; cin >> n; long long ans = 0; for(int i = 1; i <= n; i++) { haha[i][0] = 0; haha[i][1] = 0; } for(int i = 0; i < 2*n; i++) { cin >> x >> y; if(x < 1) { ans+=1-x; x = 1; } else if(x > n) { ans+=x-n; x = n; } if(y < 1) { ans+=1-y; y = 1; } else if(y > 2) { ans+=y-2; y = 2; } haha[x][y-1]++; } int sb = 0; for(int i = 0; i <= 2*n; i++) { dp[0][i] = INT_MAX/2; } dp[0][0] = 0; for(int i = 1; i <= n; i++) { int k = haha[i][0]+haha[i][1],a = haha[i][0]; sb+=k; for(int j = 0; j <= 2*n; j++) { dp[i][j] = INT_MAX/2; } for(int j = 0; j <= 2*n; j++) { for(int y = 0; y <= k && j+y <= 2*n; y++) { dp[i][j+y] = min(dp[i][j+y],dp[i-1][j]+abs(i-(j+y))+abs(i-(sb-(j+y)))+abs(y-a)); } } } cout << ans+dp[n][n]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...