Submission #1215143

#TimeUsernameProblemLanguageResultExecution timeMemory
1215143MalixWiring (IOI17_wiring)C++20
0 / 100
17 ms6072 KiB
#include "wiring.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vii; typedef pair<int,int> pi; typedef vector<pi> pii; typedef tuple<int,int,int> ti; typedef vector<ll> li; typedef vector<li> lii; #define REP(i,a,b) for(int i=a;i<b;i++) #define F first #define S second #define PB push_back #define LSOne(s) ((s)&(-s)) ll INF=1000000000000000010; int inf=1e9+10; ll M=1e9+7; long long min_total_length(std::vector<int> r, std::vector<int> b) { int n=0,pos=0,sz=r.size()+b.size(); vector<pi> a,c; REP(i,0,r.size())a.PB({r[i],0}); REP(i,0,b.size())a.PB({b[i],1}); sort(a.begin(),a.end()); while(pos<sz){ int x=pos,y=pos; while(y+1<sz&&a[y+1].S==a[x].S)y++; pos=y+1; n++; c.PB({x,y}); } vector<vector<ll>> dp(n),pref(n),suff(n); REP(i,0,n){ dp[i].resize(c[i].S-c[i].F+2,INF); pref[i].resize(c[i].S-c[i].F+2,0); suff[i].resize(c[i].S-c[i].F+2,0); REP(j,0,c[i].S-c[i].F+1)pref[i][j+1]=pref[i][j]+(ll)a[c[i].F+j].F-(ll)a[c[i].F].F; suff[i][c[i].S-c[i].F+1]=0; for(int j=c[i].S-c[i].F-1;j>=0;j--)suff[i][j+1]=suff[i][j+2]+(ll)a[c[i].S].F-(ll)a[c[i].F+j].F; } dp[0].back()=0; REP(i,1,n){ int x=dp[i-1].size(),y=dp[i].size(); dp[i][y-1]=dp[i-1][0]; REP(j,1,x)if(dp[i-1][j]!=INF)dp[i][max(0,y-1-j)]=min(dp[i][max(0,y-1-j)],dp[i-1][j]+suff[i-1][x-j]+pref[i][min(j,y-1)]+j*(a[c[i].F].F-a[c[i-1].S].F)); for(int j=y-1;j>0;j--)if(dp[i][j]!=INF)dp[i][j-1]=min(dp[i][j-1],dp[i][j]+a[c[i].S-j+1].F-a[c[i-1].S].F); } return dp[n-1][0]; }
#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...