oj.uz

Submission #101682

# Submission time Handle Problem Language Result Execution time Memory
101682 2019-03-19T09:24:46 Z daniel920712 Wiring (IOI17_wiring) C++14
0 / 100
 1000 ms 62460 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <map>
#include <utility>
#include <vector>
#include "wiring.h"

using namespace std;
map < pair < int ,int > , long long > DP;
long long all[100005]={0};
long long F(int N,int M,vector < int > &r,vector < int > &b)
{
    if(N==M) return all[N];
    else
    {
        if(DP.find(make_pair(N,M))!=DP.end()) return DP[make_pair(N,M)];
        long long t=abs(r[N]-b[M]),x=1e18;
        if(N) x=min(x,F(N-1,M,r,b));
        if(M) x=min(x,F(N,M-1,r,b));
        if(N&&M) x=min(x,F(N-1,M-1,r,b));
        //printf("%d %d %lld\n",N,M,t+x);
        DP[make_pair(N,M)]=t+x;
        return t+x;
    }
}
long long min_total_length(vector < int > r, vector < int > b)
{
    int N=r.size();
    int M=b.size();
    int i;
    for(i=0;i<min(N,M);i++)
    {
        if(i) all[i]+=all[i-1];
        all[i]+=abs(r[i]-b[i]);
    }
    return F(N-1,M-1,r,b);
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 15 ms 1212 KB Output is correct
3 Execution timed out 1083 ms 62460 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB 3rd lines differ - on the 1st token, expected: '27', found: '30'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

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