제출 #1358013

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1358013		eliminator_101	Strange Device (APIO19_strange_device)	C++20	35 / 100	261 ms	32592 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;

#define int long long
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,a,b;
    cin>>n>>a>>b;
    vector<pair<int,int>>v(n);
    for(auto&[c,d]:v){
        cin>>c>>d;
    }
    int g = __gcd(a,b+1);
    __int128 tt = a/g*b;

    int mx = -1,ans=0;
    vector<pair<int,int>>v1;
    if(tt<=(__int128)1e18){
        for (auto[c,d]:v){
            if(d-c>tt){
                ans=tt;
                break;
            }
            int c1 = c%((int)tt);
            int d1 = d%((int)tt);
            if(c1>d1){
                v1.push_back({c1,tt-1});
                v1.push_back({0LL,d1});
            }else{
                v1.push_back({c1,d1});
            }
        }
    }
    if(ans){
        cout<<ans<<endl;
        return 0;
    }
    sort(v1.begin(), v1.end());
    for (auto[c,d]:v1){
        if (c>mx){
            ans+=d-c+1;
            mx=d;
        }else if(d>mx){ 
            ans+=d-mx;
            mx=d;
        }
    }
    cout<<ans<<endl;
    return 0;
}

• 서브태스크 1: 0 / 10
• 서브태스크 2: 0 / 5
• 서브태스크 3: 5 / 5
• 서브태스크 4: 5 / 5
• 서브태스크 5: 5 / 5
• 서브태스크 6: 20 / 20
• 서브태스크 7: 0 / 20
• 서브태스크 8: 0 / 30