oj.uz

Submission #71428

# Submission time Handle Problem Language Result Execution time Memory
71428 2018-08-24T13:37:04 Z Kmcode Wiring (IOI17_wiring) C++14
10 / 100
 273 ms 192172 KB 
#include<bits/stdc++.h>
//#include "books.h"
using namespace std;

#define MAX 100002
int n;
long long int dp[MAX][110];
int pos[MAX];
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	for(int i=0;i<r.size();i++){
		for(int j=0;j<200;j++){
			dp[i][j]=LLONG_MAX;
		}
		pos[i]=lower_bound(b.begin(),b.end(),r[i])-b.begin();
	}
	int x=50;
	dp[0][0-pos[0]+x]=abs(r[0]-b[0]);
	for(int i=0;i<r.size();i++){
		for(int j1=0;j1<100;j1++){
			int j=pos[i]+j1-x;
			if(j<0||j>=b.size())continue;
			if(dp[i][j1]==LLONG_MAX)continue;
			long long int val=dp[i][j1];
			if(i+1<r.size()){
				int base=pos[i+1]-x;
				if(j-base>=0)dp[i+1][j-base]=min(dp[i+1][j-base],val+(long long int)abs(r[i+1]-b[j]));
			}
			if(j+1<b.size()){
				int base=pos[i]-x;
				if(j+1-base>=0)dp[i][j+1-base]=min(dp[i][j+1-base],val+(long long int)abs(r[i]-b[j+1]));
			}
			if(i+1<r.size()&&j+1<b.size()){
				int base=pos[i+1]-x;
				if(j+1-base>=0)dp[i+1][j+1-base]=min(dp[i+1][j+1-base],val+(long long int)abs(r[i+1]-b[j+1]));
			}
		}
	}
	return dp[r.size()-1][b.size()-1-pos[r.size()-1]+x];
}

Compilation message

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]
  for(int i=0;i<r.size();i++){
              ~^~~~~~~~~
wiring.cpp:18:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<r.size();i++){
              ~^~~~~~~~~
wiring.cpp:21:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(j<0||j>=b.size())continue;
            ~^~~~~~~~~~
wiring.cpp:24:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(i+1<r.size()){
       ~~~^~~~~~~~~
wiring.cpp:28:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(j+1<b.size()){
       ~~~^~~~~~~~~
wiring.cpp:32:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(i+1<r.size()&&j+1<b.size()){
       ~~~^~~~~~~~~
wiring.cpp:32:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(i+1<r.size()&&j+1<b.size()){
                     ~~~^~~~~~~~~
wiring.cpp:12:12: warning: iteration 110 invokes undefined behavior [-Waggressive-loop-optimizations]
    dp[i][j]=LLONG_MAX;
            ^
wiring.cpp:11:16: note: within this loop
   for(int j=0;j<200;j++){
               ~^~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 2 ms 564 KB Output is correct
6 Correct 3 ms 564 KB Output is correct
7 Incorrect 3 ms 668 KB 3rd lines differ - on the 1st token, expected: '445668', found: '9223372036854775807'
8 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 844 KB Output is correct
2 Correct 3 ms 844 KB Output is correct
3 Correct 261 ms 88628 KB Output is correct
4 Correct 227 ms 90204 KB Output is correct
5 Correct 2 ms 90204 KB Output is correct
6 Correct 3 ms 90204 KB Output is correct
7 Correct 2 ms 90204 KB Output is correct
8 Correct 4 ms 90204 KB Output is correct
9 Correct 3 ms 90204 KB Output is correct
10 Correct 3 ms 90204 KB Output is correct
11 Correct 4 ms 90204 KB Output is correct
12 Correct 3 ms 90204 KB Output is correct
13 Correct 3 ms 90204 KB Output is correct
14 Correct 3 ms 90204 KB Output is correct
15 Correct 3 ms 90204 KB Output is correct
16 Correct 3 ms 90204 KB Output is correct
17 Correct 3 ms 90204 KB Output is correct
18 Correct 238 ms 91980 KB Output is correct
19 Correct 209 ms 93784 KB Output is correct
20 Correct 256 ms 96240 KB Output is correct
21 Correct 263 ms 97676 KB Output is correct
22 Correct 273 ms 99860 KB Output is correct
23 Correct 239 ms 102064 KB Output is correct
24 Correct 251 ms 103932 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 103932 KB Output is correct
2 Runtime error 260 ms 192172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 2 ms 564 KB Output is correct
6 Correct 3 ms 564 KB Output is correct
7 Incorrect 3 ms 668 KB 3rd lines differ - on the 1st token, expected: '445668', found: '9223372036854775807'
8 Halted 0 ms 0 KB -