제출 #429005

#제출 시각아이디문제언어결과실행 시간메모리
429005REALITYNB전선 연결 (IOI17_wiring)C++14
13 / 100
75 ms10712 KiB
#include <bits/stdc++.h> #include "wiring.h" #define ll long long #define all(a) a.begin(),a.end() #define pb push_back using namespace std; const ll inf = 1e18 ; ll min_total_length(vector<int> r,vector<int> bb){ vector<ll> a ; for(int&x:r) ++x ; for(int&x: bb) ++x; for(ll x:r) a.pb(x) ; for(ll x:bb) a.pb(-x) ; sort(all(a),[&](ll x,ll y){return abs(x) <abs(y) ; }); ll n = a.size() ; vector<vector<ll>> b ; for(ll i=0;i<n;i++){ ll sz = 0 ; vector<ll> hey ; for(ll j=i;j<n;j++){ if(a[i]*a[j]<0) break ; hey.pb(j); i=j ; } b.pb(hey); } for(ll&x:a)if(x<0) x*=-1 ; for(ll&x:a) --x; /*cout << b.size() << endl ; for(auto x :b){ for(ll y:x) cout << y << " "; cout << endl ; }*/ vector<ll> dp(n,inf) ; ll sumi = 0 ; for(ll x:b[0]) sumi+=a[x] ; ll loli = a[b[1][0]]*(b[0].size()) ; for(ll i=0;i<b[1].size();i++){ loli+=a[b[1][i]]; if(i+1>b[0].size()){ sumi+=a[b[0].back()]; } else loli-=a[b[1][0]]; // cout << loli << " " << sumi << " "<< a[b[1][0]] << endl ; dp[b[1][i]]=loli-sumi ; } dp[b[0].back()]=dp[b[1][0]]; for(ll i=2;i<b.size();i++){ ll prev = dp[b[i-1].back()] ; ll lol = b[i-1].back(); ll sum = 0 ; for(ll j=0;j<b[i].size();j++){ prev+=a[b[i][j]]; prev-=a[b[i-1].back()] ; if(lol-j>=b[i-1][0]){ sum+=a[b[i][j]]; sum-=a[lol-j]; prev=min(prev,dp[lol-j-1]+sum) ; } dp[b[i][j]]=min(dp[b[i][j]],prev) ; } ll mn = min(b[i].size(),b[i-1].size()) ; prev=inf; sum = 0; for(ll j=0;j<mn;j++) sum+=a[b[i][j]]; for(ll j=b[i-1].size()-1;j>lol-mn;j--) sum-=a[b[i-1][j]]; for(ll j=mn-1;j>-1;j--){ prev=min(prev,sum+dp[lol-j-1]) ; dp[b[i][j]]=min(dp[b[i][j]],prev) ; prev-=a[b[i][j]]; prev+=a[b[i][0]]; sum-=a[b[i][j]] ; sum+=a[lol-j]; } } // for(ll x: dp) cout << x << " " ; return dp.back() ; }

컴파일 시 표준 에러 (stderr) 메시지

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:18:12: warning: unused variable 'sz' [-Wunused-variable]
   18 |         ll sz = 0 ;
      |            ^~
wiring.cpp:38:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(ll i=0;i<b[1].size();i++){
      |                ~^~~~~~~~~~~~
wiring.cpp:40:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         if(i+1>b[0].size()){
      |            ~~~^~~~~~~~~~~~
wiring.cpp:49:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(ll i=2;i<b.size();i++){
      |                ~^~~~~~~~~
wiring.cpp:53:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(ll j=0;j<b[i].size();j++){
      |                    ~^~~~~~~~~~~~
#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...