제출 #1246834

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246834		stanirina	Parkovi (COCI22_parkovi)	C++20	0 / 110	118 ms	1948 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;
int n,k;
vector<int> w;

bool proveri(int dist){
    int cnt=0ll;
    int i=0ll;
    int sum=0ll;
    while(i<n-1ll){
        if(sum+w[i]>dist){
            sum=0ll;
            cnt++;
            while(sum<dist && i<n-1ll){
                sum+=w[i];
                if(sum>dist)break;
                i++;
            }
            sum=0ll;
            i++;
        }
        else{
            i++;
            sum+=w[i];
        }
    }
    if(cnt>k)return false;
    return true;
}

int32_t main()
{
    cin>>n>>k;
    w.resize(n-1);
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        cin>>w[i];
    }
    int maxedge=0ll;
    for(int i=0;i<n-1;i++)maxedge=max(maxedge,w[i]);
    int l=0ll;
    int r=100000000000000000ll;
    while(l<=r){
        int mid=l+(r-l)/2ll;
        //cout<<mid<<endl;
        if(proveri(mid))r=mid-1ll;
        else l=mid+1ll;
    }
    cout<<l<<endl;
    int cnt=0ll;
    int i=0ll;
    int sum=0ll;
    while(i<n-1ll){
        if(sum+w[i]>l){
            cout<<i+1<<' ';
            sum=0ll;
            cnt++;
            while(sum<l && i<n-1ll){
                sum+=w[i];
                if(sum>l)break;
                i++;
            }

            sum=0ll;
            i++;
        }
        else{
            i++;
            sum+=w[i];
        }
    }

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60