oj.uz

Submission #411064

# Submission time Handle Problem Language Result Execution time Memory
411064 2021-05-24T08:37:19 Z 조영욱(#7633) Constellation 3 (JOI20_constellation3) C++17
0 / 100
 25 ms 31564 KB 
#include <bits/stdc++.h>
using namespace std;

int arr[200001];
typedef pair<int,int> P;
typedef pair<P,int> Pi;
long long dp[2001][2001]; //dp[ind][y]
vector<Pi> v;

long long ans(int ind,int y) {
    if (ind==v.size()) {
        return 0;
    }
    if (dp[ind][y]!=-1) {
        return dp[ind][y];
    }
    int ny=y;
    for(int i=(ind==0?1:v[ind-1].first.first+1);i<=v[ind].first.first;i++) {
        if (arr[i]>=y) {
            ny=0;
            break;
        }
    }
    long long ret=0;
    if (ny==0) {
        ret=max(ret,ans(ind+1,0));
        ret=max(ret,ans(ind+1,v[ind].first.second)+v[ind].second);
    }
    else {
        ret=max(ret,ans(ind+1,ny));
    }
    return dp[ind][y]=ret;
}

int main(void) {
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&arr[i]);
    }
    int m;
    scanf("%d",&m);
    long long ret=0;
    long long sum=0;
    for(int i=0;i<m;i++) {
        int x,y,c;
        scanf("%d %d %d",&x,&y,&c);
        v.push_back(Pi(P(x,y),c));
        ret=max(ret,(long long)c);
        sum+=c;
    }
    sort(v.begin(),v.end());
    memset(dp,-1,sizeof(dp));
    ret=max(ret,ans(0,0));
    printf("%lld",sum-ret);
}

Compilation message

constellation3.cpp: In function 'long long int ans(int, int)':
constellation3.cpp:11:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     if (ind==v.size()) {
      |         ~~~^~~~~~~~~~
constellation3.cpp: In function 'int main()':
constellation3.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
constellation3.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         scanf("%d",&arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~
constellation3.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%d",&m);
      |     ~~~~~^~~~~~~~~
constellation3.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf("%d %d %d",&x,&y,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 31564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 31564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 31564 KB Output isn't correct
2 Halted 0 ms 0 KB -