oj.uz

Submission #879073

# Submission time Handle Problem Language Result Execution time Memory
879073 2023-11-26T09:06:50 Z snpmrnhlol Wiring (IOI17_wiring) C++17
0 / 100
 33 ms 10048 KB 
#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5;
const ll inf = 2e9;
vector <ll> a;
vector <ll> c;
struct p{
    ll nr,tip;
}v[2*N];
ll dp[2*N];
ll ps[2*N + 1];
ll sum(ll l,ll r){
    return ps[r + 1] - ps[l];
}
ll min_total_length(vector <int> r,vector <int> b){
    ll n = 0;
    for(ll i = 0;i < r.size();i++){
        v[n++] = {r[i],0};
    }
    for(ll i = 0;i < b.size();i++){
        v[n++] = {b[i],1};
    }
    sort(v,v + n,[&](p a,p b){
         return a.nr < b.nr;
    });
    for(ll i = 0;i < n;i++){
        ps[i + 1] = ps[i] + v[i].nr;
        dp[i] = inf;
    }
    ll i = 0,p = -1;
    while(i < n){
        ll nxt = i;
        while(nxt < n - 1 && v[i].tip == v[nxt + 1].tip)nxt++;
        if(p != -1){
            ///p index of first red
            ///i index of first blue
            ///nxt index of last blue
            ///case 1: right side bigger
            ll l = i - 1;
            ll r = i;
            ll cross = (v[i].nr - v[i - 1].nr);
            ll minn = inf;
            while(l >= p && r <= nxt){
                minn = min(minn,(l == 0?0:dp[l - 1]) + ((i - l)*v[i - 1].nr - sum(l,i - 1)));
                //cout<<minn<<' '<<(r - i + 1)*cross<<' '<<sum(i,r)<<' '<<'\n';
                dp[r] = min(dp[r],(r - i + 1)*cross + (sum(i,r) - v[i].nr*(r - i + 1)) + minn);
                l--;r++;
            }
            while(r <= nxt){
                //cout<<minn<<' '<<(r - i + 1)*cross<<' '<<sum(i,r)<<' '<<'\n';
                dp[r] = min(dp[r],(r - i + 1)*cross + (sum(i,r) - v[i].nr*(r - i + 1)) + minn);
                r++;
            }

            ///case 2:left side bigger
            l = p;
            r = nxt;
            minn = inf;
            while(i - 1 - l > r - i){
                minn = min(minn,(l == 0?0:dp[l - 1]) + (i - l)*cross + v[i - 1].nr*(i - l) - sum(l,i - 1));
                l++;
            }
            while(i - 1 - l < r - i){
                r--;
            }
            while(l < i && r > i - 1){
                minn = min(minn,(l == 0?0:dp[l - 1]) + (i - l)*cross + v[i - 1].nr*(i - l) - sum(l,i - 1));
                //cout<<r<<' '<<minn<<' '<<sum(i,r)<<' '<<v[i].nr*(r - i + 1)<<'\n';
                dp[r] = min(dp[r],sum(i,r) - v[i].nr*(r - i + 1) + minn);
                l++;
                r--;
            }
            /*for(ll j = 0;j < n;j++){
                cout<<dp[j]<<' ';
            }
            cout<<'\n';*/
        }
        p = i;
        i = nxt;
        i++;
    }
    return dp[n - 1];
}
/**
int main(){
    ll n,m;
    cin>>n>>m;
    a.resize(n);
    c.resize(m);
    for(ll i = 0;i < n;i++){
        cin>>a[i];
    }
    for(ll i = 0;i < m;i++){
        cin>>c[i];
    }
    min_total_length(a,c);
    return 0;
}
**/
/**
4 5
1 2 3 7
0 4 5 9 10
**/

Compilation message

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:19:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(ll i = 0;i < r.size();i++){
      |                  ~~^~~~~~~~~~
wiring.cpp:22:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(ll i = 0;i < b.size();i++){
      |                  ~~^~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 1 ms 4444 KB 3rd lines differ - on the 1st token, expected: '14340', found: '14694'
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Incorrect 24 ms 8452 KB 3rd lines differ - on the 1st token, expected: '41596985758595', found: '2000000000'
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4596 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 33 ms 10048 KB 3rd lines differ - on the 1st token, expected: '1068938599', found: '1152497305'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 28 ms 9352 KB Output is correct
3 Correct 31 ms 9304 KB Output is correct
4 Correct 31 ms 9296 KB Output is correct
5 Correct 30 ms 9308 KB Output is correct
6 Incorrect 1 ms 4440 KB 3rd lines differ - on the 1st token, expected: '42', found: '43'
7 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 1 ms 4444 KB 3rd lines differ - on the 1st token, expected: '14340', found: '14694'
3 Halted 0 ms 0 KB -