Submission #56258

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
56258	2018-07-10 17:47:45	ngkan146	Wiring (IOI17_wiring)	C++11	100 / 100	83 ms	13580 KiB

wiring

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "wiring.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<int,int> ii;
ll dp[200005], prefixSum[200005], rem[200005];
ll min_total_length(vector<int> r, vector<int> b) {
    vector <ii> lst;
    int piR = 0, piB = 0;
    while(piR < r.size() || piB < b.size()){
        if (piR == r.size())
            lst.push_back(ii(b[piB++], 2));
        else if (piB == b.size())
            lst.push_back(ii(r[piR++], 1));
        else{
            if (r[piR] < b[piB])
                lst.push_back(ii(r[piR++], 1));
            else
                lst.push_back(ii(b[piB++], 2));
        }
    }
    piR = 0, piB = 0;
    int slope = 0, lrange = 0, rrange = 0;
    r.push_back((int)2e9+5);
    b.push_back((int)2e9+5);
    for(int i=0;i<lst.size();i++){
        dp[i+1] = (ll) 1e18;
        prefixSum[i+1] = prefixSum[i] + (lst[i].second == 1 ? 1 : -1) * lst[i].first;
        slope += (lst[i].second == 1 ? 1 : -1);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:10:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(piR < r.size() || piB < b.size()){
           ~~~~^~~~~~~~~~
wiring.cpp:10:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(piR < r.size() || piB < b.size()){
                             ~~~~^~~~~~~~~~
wiring.cpp:11:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (piR == r.size())
             ~~~~^~~~~~~~~~~
wiring.cpp:13:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         else if (piB == b.size())
                  ~~~~^~~~~~~~~~~
wiring.cpp:26:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<lst.size();i++){
                 ~^~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45