Submission #1063470

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063470		Ahmed57	Treatment Project (JOI20_treatment)	C++17	0 / 100	100 ms	12516 KiB

treatment

#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 (stderr)

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
• Subtask 2: 0 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 61