Submission #853534

#TimeUsernameProblemLanguageResultExecution timeMemory
853534abcvuitunggioAliens (IOI16_aliens)C++17
25 / 100
92 ms25436 KiB
#include "aliens.h" #include <bits/stdc++.h> #define int long long using namespace std; const int INF=1e18; int n,dp[501][501],s[100001],e[100001],mn[100001],mx[1000001]; vector <pair <int, int>> ve; int f(int i, int j){ if (j<0) return INF; if (i==n) return 0; if (dp[i][j]!=-1) return dp[i][j]; dp[i][j]=INF; for (int k=i;k<n;k++) dp[i][j]=min(dp[i][j],f(k+1,j-1)+(mn[k]-s[i])*(e[k]*2-s[i]-mn[k]+2)); return dp[i][j]; } long long take_photos(int32_t N, int32_t M, int32_t K, vector <int32_t> R, vector <int32_t> C){ memset(mx,-1,sizeof(mx)); memset(dp,-1,sizeof(dp)); for (int i=0;i<N;i++) mx[min(R[i],C[i])]=max(mx[min(R[i],C[i])],(int)max(R[i],C[i])); for (int i=0;i<M;i++) if (mx[i]!=-1) ve.emplace_back(i,mx[i]); sort(ve.begin(),ve.end()); int cur=-1; for (auto [i,j]:ve) if (j>cur){ s[n]=i; e[n]=j; n++; cur=j; } s[n]=INF; for (int i=0;i<n;i++) mn[i]=min(s[i+1],e[i]+1); return f(0,K); }
#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...