Submission #135557

#TimeUsernameProblemLanguageResultExecution timeMemory
135557ckodserAliens (IOI16_aliens)C++14
25 / 100
1427 ms6596 KiB
#include "aliens.h" #include<bits/stdc++.h> #define ll int #define pb push_back #define mp make_pair #define ld long double #define F first #define S second #define pii pair<ll,ll> using namespace :: std; const ll maxn=4100; const ll maxk=4010; const ll inf=1e9+900; const ll logg=20; ll tav2(ll x){ return x*x; } ll mx[maxn]; ll dp[maxn][maxk]; ll ff[maxn][logg]; ll tt[maxn]; ll findMn(ll l,ll r){ ll tol=r-l+1; return min(ff[l][tt[tol]],ff[r-(1<<tt[tol])+1][tt[tol]]); } ll cost(ll i,ll x){ ll t=findMn(x+1,i); if(x==-1)return tav2(i-t+1); if(mx[x]>=t){ return inf; } if(t>x){ return tav2(i-t+1); } return tav2(i-t+1)-tav2(x-t+1); } long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { swap(n,m); fill(mx,mx+maxn,inf); for(ll i=0;i<m;i++){ if(c[i]>r[i]){ swap(c[i],r[i]); } mx[r[i]]=min(mx[r[i]],(ll)c[i]); } for(ll i=0;i<n;i++){ ff[i][0]=mx[i]; } tt[1]=0; for(ll i=2;i<maxn;i++){ tt[i]=tt[i/2]+1; } for(ll i=1;i<logg;i++){ for(ll j=0;j<n;j++){ ll res=j+(1<<(i-1)); if(res>=n){ ff[j][i]=ff[j][i-1]; }else{ ff[j][i]=min(ff[j][i-1],ff[res][i-1]); } } } for(ll i=1;i<=n;i++){ for(ll j=0;j<=k;j++){ if(mx[i-1]==inf){ dp[i][j]=dp[i-1][j]; }else{ if(j==0){ dp[i][j]=inf; }else{ dp[i][j]=inf; for(ll x=i-1;x>=0;x--){ dp[i][j]=min(dp[i][j],dp[x][j-1]+cost(i-1,x-1)); } } } } } return dp[n][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...