제출 #301696

#제출 시각아이디문제언어결과실행 시간메모리
301696TMJN전선 연결 (IOI17_wiring)C++17
0 / 100
1 ms384 KiB
#include "wiring.h" #include <bits/stdc++.h> using namespace std; long long DP[400][210][2]; int N; vector<pair<long long,bool>>V; long long min_total_length(vector<int>r,vector<int>b){ for(int i:r){ V.push_back({i,0}); } for(int i:b){ V.push_back({i,1}); } N=V.size(); sort(V.begin(),V.end()); for(int i=0;i<N;i++){ for(int j=0;j<210;j++){ for(int k=0;k<2;k++){ DP[i][j][k]=0xE869120E869120; } } } for(int i=1;i<=200;i++){ DP[0][i][V[0].second]=0; } for(int i=1;i<N;i++){ DP[i-1][0][0]=DP[i-1][0][1]=min(DP[i-1][0][0],DP[i-1][0][1]); for(int j=200;j>=0;j--){ DP[i][j][!V[i].second]=min(DP[i][j+1][!V[i].second],DP[i-1][j+1][!V[i].second]+(j+1)*(V[i].first-V[i-1].first)); } DP[i][0][V[i].second]=DP[i][0][!V[i].second]; for(int j=0;j<=200;j++){ DP[i][j][V[i].second]=min(DP[i][0][V[i].second],(j?DP[i-1][j-1][V[i].second]:0xE869120E869120)); } } return min(DP[N-1][0][0],DP[N-1][0][1]); }
#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...