#709331 (C++14) No.1715 Dinner 2

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#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