abc C 求调
  • 板块学术版
  • 楼主littlebug
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/11/9 21:54
  • 上次更新2024/11/10 09:17:41
查看原帖
abc C 求调
541634
littlebug楼主2024/11/9 21:54

WA 3,不知道漏掉了什么特判之类的东西(

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define int long long
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rpe(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair <int,int>
#define mp make_pair
#define st first
#define nd second
#define pb emplace_back
using namespace std;

const int MAXN=2e5+5;
int n,m;
pii a[MAXN];
vector <pii> v;

il int calc(int x,int l,int r)
{
    return ((l-x)+(r-x))*(r-l+1)/2;
}

il int sol(int l,int cos)
{
    int res=0;
    while(cos>0 && !v.empty())
    {
        if(cos>=v.back().nd-v.back().st+1) cos-=v.back().nd-v.back().st+1,res+=calc(l,v.back().st,v.back().nd),v.pop_back();
        else res+=calc(l,v.back().nd-cos+1,v.back().nd),v.back().nd-=cos,cos=0;
    }

    return res;
}

signed main()
{
    ios::sync_with_stdio(0); ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);

    cin>>n>>m;
    int sum=0;
    rep(i,1,m) cin>>a[i].st;
    rep(i,1,m) cin>>a[i].nd,sum+=a[i].nd;
    sort(a+1,a+m+1);

    if(sum!=n) return cout<<-1,0;

    a[m+1]=mp(n+1,5201314);
    int res=0,ans=0;
    rpe(i,m,1)
    {
        v.pb(a[i].st+1,a[i+1].st-1);
        res+=a[i+1].st-a[i].st-1;

        if(a[i].nd>res+1) return cout<<-1,0;
        else if(a[i].nd==res+1) ans+=sol(a[i].st,a[i].nd),vector<pii>().swap(v),res=0;
        else if(a[i].nd==res) ans+=sol(a[i].st,a[i].nd),vector<pii>().swap(v),res=0;
        else if(a[i].nd<res) ans+=sol(a[i].st,a[i].nd),res-=a[i].nd,++a[i].st;
    }

    cout<<(res>0 ? -1 : ans);

    return 0;
}

喜提只会 ABDF,F 还挂了

2024/11/9 21:54
加载中...