oj.uz

Submission #1063470

# Submission time Handle Problem Language Result Execution time Memory
1063470 2024-08-17T19:06:51 Z Ahmed57 Treatment Project (JOI20_treatment) C++17
0 / 100
 100 ms 12516 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long
#pragma GCC optimize("Ofast")
vector<array<int,4>> rng;
int n;
map<pair<int,int>,int> dp[5001];
int solve(int l,int r,int i){
    if(l>r)return 0;
    if(i==rng.size()){
        return 1e18;
    }
    if(dp[i].find(make_pair(l,r))!=dp[i].end())return dp[i][{l,r}];
    int L = max(1ll,l-(rng[i][0]-rng[i-1][0])) , R = min(n,r+(rng[i][0]-rng[i-1][0]));
    long long c1 = solve(L,R,i+1);
    if(rng[i][2]<L||rng[i][1]>R){

    }else{
        long long fi = 0;
        if(rng[i][1]>L){
            fi+=solve(L,rng[i][1]-1,i+1);
        }
        if(rng[i][2]<R){
            fi+=solve(rng[i][2]+1,R,i+1);
        }
        c1 = min(c1,fi+rng[i][3]);
    }
    return dp[i][{l,r}] = c1;
}
signed main(){
    int m;cin>>n>>m;
    rng.push_back({0,1,n,0});
    for(int i = 0;i<m;i++){
        int x,l,r,c;
        cin>>x>>l>>r>>c;
        rng.push_back({x,l,r,c});
    }
    sort(rng.begin(),rng.end());
    cout<<solve(1,n,1)<<endl;
}

Compilation message

treatment.cpp: In function 'long long int solve(long long int, long long int, long long int)':
treatment.cpp:10:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     if(i==rng.size()){
      |        ~^~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 100 ms 12516 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Incorrect 0 ms 604 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Incorrect 0 ms 604 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Runtime error 100 ms 12516 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -