제출 #567063

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
567063		tqbfjotld	Sightseeing in Kyoto (JOI22_kyoto)	C++14	40 / 100	2086 ms	214180 KiB

kyoto

#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 tt = i1.first*(-i4.second-i2.second)+i2.first*(-i3.second-i1.second);
    int ans = recl(i1.second,i2.second)+recr(-i3.second,-i4.second)+tt;
    printf("%lld",ans);
}

컴파일 시 표준 에러 (stderr) 메시지

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: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 0 / 60