結果

問題 No.1715 Dinner 2
ユーザー publfl
提出日時 2021-10-22 22:03:58
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 1,723 bytes
コンパイル時間 355 ms
コンパイル使用メモリ 50,816 KB
実行使用メモリ 7,108 KB
最終ジャッジ日時 2024-09-23 05:34:08
合計ジャッジ時間 1,544 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
#include <vector>
#define MIN -1234567890
std::vector< std::pair<int,int> > V[100010];
std::pair<int,int> x[100010],y[100010];
std::pair<int,int> W[1010];
int main()
{
int a,b;
scanf("%d%d",&a,&b);
for(int i=1;i<=a;i++)
{
int c,d;
scanf("%d%d",&c,&d);
V[c].push_back(std::make_pair(d-c,i));
W[i] = std::make_pair(c,d);
}
std::pair<int,int> max1 = std::make_pair(MIN,0);
std::pair<int,int> max2 = max1;
for(int i=0;i<=100000;i++)
{
for(int j=0;j<V[i].size();j++)
{
if(max1.first <=V[i][j].first) max2 = max1, max1 = V[i][j];
else if(max2.first <= V[i][j].first) max2 = V[i][j];
}
x[i] = max1, y[i] = max2;
}
long long int min = MIN, max = 0;
long long int ans = MIN;
while(min<=max)
{
long long int h = (min+max)/2;
int prev = -1;
long long int s = -h;
for(int i=1;i<=b-2;i++)
{
long long int t = s<100000?s:100000;
if(x[t].second==0)
{
max = h-1;
goto u;
}
else if(prev==x[t].second)
{
if(y[t].second==0)
{
max = h-1;
goto u;
}
else
{
s += (y[t].first);
prev = y[t].second;
}
}
else
{
s += (x[t].first);
prev = x[t].second;
}
}
for(int i=1;i<=a;i++)
{
if(i==prev) continue;
if(s<W[i].first) continue;
long long int s2 = s + (W[i].second-W[i].first);
if(s2>100000)
{
ans = h;
min = h+1;
goto u;
}
else if(s2<0);
else if(x[s2].second==0);
else
{
if(x[s2].second==i)
{
if(y[s2].second==0);
else
{
ans = h;
min = h+1;
goto u;
}
}
else
{
ans = h;
min = h+1;
goto u;
}
}
}
max = h-1;
u:;
}
printf("%lld",ans);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0