oj.uz

Submission #567054

# Submission time Handle Problem Language Result Execution time Memory
567054 2022-05-23T07:41:53 Z tqbfjotld Sightseeing in Kyoto (JOI22_kyoto) C++14
0 / 100
 293 ms 29008 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 999999999999999999LL;

int arr1[100005];
int arr2[100005];

struct node{
    int s,e;
    pair<int,int> v;
    node *l,*r;
    node (int _s, int _e, bool arr, bool lr){
        s = _s; e = _e;
        if (s==e){
            v = make_pair((arr?arr1:arr2)[s],lr?s:-s);
        }
        if (s!=e){
            l = new node(s,(s+e)/2,arr,lr);
            r = new node((s+e)/2+1,e,arr,lr);
            v = min(l->v,r->v);
        }
    }
    pair<int,int> qu(int a, int b){
        if (a<=s && e<=b){
            return v;
        }
        if (b<=(s+e)/2){
            return l->qu(a,b);
        }
        if (a>(s+e)/2){
            return r->qu(a,b);
        }
        return min(l->qu(a,b),r->qu(a,b));
    }
}*r1,*r2,*r3,*r4;

map<pair<int,int>,int> m1,m2;

set<int> s1,s2;

int recl(int a, int b){
    //printf("call recl %lld %lld\n",a,b);
    if (a==0) return arr1[0]*b;
    if (b==0) return arr2[0]*a;
    if (m1.count({a,b})) return m1[{a,b}];
    auto opt1 = r1->qu(0,a-1);
    auto opt2 = r2->qu(0,b-1);
    return m1[{a,b}] = min(recl(opt1.second,b)+arr2[b]*(a-opt1.second),recl(a,opt2.second)+arr1[a]*(b-opt2.second));
}

int n,m;

int recr(int a, int b){
    //printf("call recr %lld %lld\n",a,b);
    if (a==n-1) return arr1[n-1]*(m-1-b);
    if (b==m-1) return arr2[m-1]*(n-1-a);
    if (m2.count({a,b})) return m2[{a,b}];
    auto opt1 = r3->qu(a+1,n-1);
    auto opt2 = r4->qu(b+1,m-1);
    return m2[{a,b}] = min(recr(-opt1.second,b)+arr2[b]*(-opt1.second-a),recr(a,-opt2.second)+arr1[a]*(-opt2.second-b));
}

 main(){

    scanf("%lld%lld",&n,&m);
    for (int x = 0; x<n; x++){
        scanf("%lld",&arr1[x]);
    }
    for (int x = 0; x<m; x++){
        scanf("%lld",&arr2[x]);
    }
    r1 = new node(0,n-1,true,true);
    r2 = new node(0,m-1,false,true);
    r3 = new node(0,n-1,true,false);
    r4 = new node(0,m-1,false,false);
    auto i1 = r1->qu(0,n-1);
    auto i2 = r2->qu(0,m-1);
    auto i3 = r3->qu(0,n-1);
    auto i4 = r4->qu(0,m-1);
    int ans = recl(i1.second,i2.second)+recr(-i3.second,-i4.second);
    printf("%lld",ans);
}

Compilation message

kyoto.cpp:65:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   65 |  main(){
      |  ^~~~
kyoto.cpp: In function 'int main()':
kyoto.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     scanf("%lld%lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
kyoto.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         scanf("%lld",&arr1[x]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
kyoto.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         scanf("%lld",&arr2[x]);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 253 ms 23136 KB Output is correct
14 Correct 3 ms 852 KB Output is correct
15 Correct 2 ms 852 KB Output is correct
16 Correct 293 ms 29008 KB Output is correct
17 Incorrect 1 ms 724 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

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

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 253 ms 23136 KB Output is correct
14 Correct 3 ms 852 KB Output is correct
15 Correct 2 ms 852 KB Output is correct
16 Correct 293 ms 29008 KB Output is correct
17 Incorrect 1 ms 724 KB Output isn't correct
18 Halted 0 ms 0 KB -