oj.uz

답안 #376383

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
376383 2021-03-11T10:48:57 Z urd05 Salesman (IOI09_salesman) C++14
100 / 100
 3000 ms 65536 KB 
# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
using namespace std;
 
const int sz=524288;
 
struct SegmentTree {
    long long seg[sz*2];
    long long lazy[sz*2];
    void init() {
        for(int i=1;i<sz*2;i++) {
            seg[i]=-1e12;
            lazy[i]=-1e12;
        }
    }
    void propagate(int node) {
        if (node<sz) {
            lazy[node*2]=max(lazy[node*2],lazy[node]);
            lazy[node*2+1]=max(lazy[node*2+1],lazy[node]);
        }
        seg[node]=max(seg[node],lazy[node]);
    }
    long long sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
        propagate(node);
        if (l>r||r<nodel||l>noder) {
            return -1e12;
        }
        if (l<=nodel&&noder<=r) {
            return seg[node];
        }
        int mid=(nodel+noder)/2;
        return max(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,noder));
    }
    void update(int l,int r,long long val,int node=1,int nodel=0,int noder=sz-1) {
        propagate(node);
        if (r<nodel||l>noder) {
            return;
        }
        if (l<=nodel&&noder<=r) {
            lazy[node]=max(lazy[node],val);
            propagate(node);
            return;
        }
        int mid=(nodel+noder)/2;
        update(l,r,val,node*2,nodel,mid);
        update(l,r,val,node*2+1,mid+1,noder);
        seg[node]=max(seg[node*2],seg[node*2+1]);
    }
};
 
SegmentTree st1; //val[i]+Di
SegmentTree st2; //val[i]-Ui
long long dp[500000];
long long le[500000];
long long ri[500000];
long long psum[500001];
 
int n,u,d,s;
typedef pair<int,int> P;
vector<P> vec[500001];
 
int main(void) {
    scanf("%d %d %d %d",&n,&u,&d,&s);
    for(int i=0;i<n;i++) {
        int t,l,m;
        scanf("%d %d %d",&t,&l,&m);
        vec[t].push_back(P(l,m));
    }
    st1.init();
    st2.init();
    st1.update(s,s,d*s);
    st2.update(s,s,-u*s);
    for(int i=1;i<=500000;i++) {
        if (vec[i].empty()) {
            continue;
        }
        sort(vec[i].begin(),vec[i].end());
        psum[0]=0;
        for(int j=1;j<=vec[i].size();j++) {
            psum[j]=psum[j-1]+vec[i][j-1].second;
        }
        for(int j=0;j<vec[i].size();j++) {
            le[j]=-1e12;
            ri[j]=-1e12;
            dp[j]=max(st1.sum(0,vec[i][j].first)-d*vec[i][j].first,st2.sum(vec[i][j].first,sz-1)+u*vec[i][j].first);
        }
        for(int j=0;j<vec[i].size();j++) {
            st1.update(vec[i][j].first,vec[i][j].first,dp[j]+d*vec[i][j].first);
            st2.update(vec[i][j].first,vec[i][j].first,dp[j]-u*vec[i][j].first);
        }
        long long mx=st1.sum(0,vec[i][0].first);
        for(int j=0;j<vec[i].size();j++) {
            le[j]=max(le[j],mx+psum[j+1]-d*vec[i][j].first);
            if (j+1!=vec[i].size())
                mx=max(mx,st1.sum(vec[i][j].first+1,vec[i][j+1].first)-psum[j+1]);
        }
        mx=st2.sum(vec[i].back().first,sz-1)+psum[vec[i].size()];
        for(int j=vec[i].size()-1;j>=0;j--) {
            ri[j]=max(ri[j],mx+u*vec[i][j].first-psum[j]);
            if (j)
                mx=max(mx,st2.sum(vec[i][j-1].first,vec[i][j].first-1)+psum[j]);
        }
        for(int j=0;j<vec[i].size();j++) {
            long long val=max(le[j],ri[j]);
            st1.update(vec[i][j].first,vec[i][j].first,val+d*vec[i][j].first);
            st2.update(vec[i][j].first,vec[i][j].first,val-u*vec[i][j].first);
        }
    }
    long long ret=0;
    for(int i=0;i<sz;i++) {
        long long val=max(st1.sum(i,i)-d*i,st2.sum(i,i)+u*i);
        if (i<s) {
            val-=d*(s-i);
        }
        else {
            val-=u*(i-s);
        }
        ret=max(ret,val);
    }
    printf("%lld",ret);
}

Compilation message

salesman.cpp: In function 'int main()':
salesman.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for(int j=1;j<=vec[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~~
salesman.cpp:85:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for(int j=0;j<vec[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~
salesman.cpp:90:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for(int j=0;j<vec[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~
salesman.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for(int j=0;j<vec[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~
salesman.cpp:97:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             if (j+1!=vec[i].size())
      |                 ~~~^~~~~~~~~~~~~~~
salesman.cpp:106:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for(int j=0;j<vec[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~
salesman.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |     scanf("%d %d %d %d",&n,&u,&d,&s);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |         scanf("%d %d %d",&t,&l,&m);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 313 ms 45036 KB Output is correct
2 Correct 313 ms 45036 KB Output is correct
3 Correct 336 ms 45036 KB Output is correct
4 Correct 315 ms 45164 KB Output is correct
5 Correct 325 ms 45292 KB Output is correct
6 Correct 407 ms 45932 KB Output is correct
7 Correct 530 ms 47340 KB Output is correct
8 Correct 761 ms 48876 KB Output is correct
9 Correct 993 ms 50464 KB Output is correct
10 Correct 1546 ms 55064 KB Output is correct
11 Correct 1685 ms 55148 KB Output is correct
12 Correct 2179 ms 58184 KB Output is correct
13 Correct 2130 ms 58184 KB Output is correct
14 Correct 2643 ms 65536 KB Output is correct
15 Correct 2311 ms 65516 KB Output is correct
16 Correct 2664 ms 65516 KB Output is correct
17 Correct 345 ms 45036 KB Output is correct
18 Correct 316 ms 45036 KB Output is correct
19 Correct 317 ms 45036 KB Output is correct
20 Correct 322 ms 45164 KB Output is correct
21 Correct 315 ms 45036 KB Output is correct
22 Correct 358 ms 45292 KB Output is correct
23 Correct 335 ms 45164 KB Output is correct
24 Correct 327 ms 45036 KB Output is correct
25 Correct 864 ms 46956 KB Output is correct
26 Correct 1311 ms 48872 KB Output is correct
27 Correct 1893 ms 51164 KB Output is correct
28 Correct 2136 ms 50680 KB Output is correct
29 Correct 3000 ms 50796 KB Output is correct
30 Correct 2804 ms 53188 KB Output is correct