QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#600766#7744. ElevatorE7kWA 42ms7724kbC++203.1kb2024-09-29 19:00:182024-09-29 19:00:19

Judging History

你现在查看的是最新测评结果

  • [2024-09-29 19:00:19]
  • 评测
  • 测评结果:WA
  • 用时:42ms
  • 内存:7724kb
  • [2024-09-29 19:00:18]
  • 提交

answer

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define gcd __gcd
using namespace std;
typedef pair<int,int> pii;
const int INF = 9e18;
const int inf = 2e9;

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    // int tt = t;
    // int u = 0;
    while(t --)
    {
        // u ++;
        int n,k;
        cin >> n >> k;
        vector<array<int,3>> a;
        for(int i = 1;i <= n;i ++)
        {
            int f,c,w;
            cin >> c >> w >> f;
            // a[i] = {f,c,w};
            if(c > 0)
            {
                a.push_back({f,c,w});
            }
        }
        sort(a.begin(),a.end());
        int ans = 0;
        vector<int> res;
        n = a.size() - 1;
        for(int i = 0;i < a.size();i ++)
        {
            if((a[i][2] & 1))
            {
                res.push_back(i);
            }
        }

        int sum = 0,lst = 0;
        for(int i = n,j = n;i >= 0;i --)
        {
            while(j >= 0 && a[j][1] <= 0) j --;
            if(sum + a[i][1] * a[i][2] <= k)
            {
                sum += a[i][1] * a[i][2];
                if(sum == k || i == 0)
                {
                    ans += a[j][0];
                    j = i - 1;
                    sum = 0;
                }
                continue;
            }

            int tep = (k - sum) / a[i][2] * a[i][2];
            lst = a[i][1] * a[i][2] - tep;
            sum += tep;
            if(sum < k)
            {
                while(res.size() && a[res.back()][0] >= a[i][0]) res.pop_back();
                if(res.size())
                {
                    auto x = res.back();
                    if(a[x][1] == 0)
                    {
                        res.pop_back();
                        continue;
                    }
                    a[x][1] --;
                    if(a[x][1] == 0) res.pop_back();
                    // res.pop_back();
                }
            }
            // if(i == 1) cout << ans << endl;
            ans += a[j][0];
            // if(i == 1) cout << 'y' << ans << endl;
            if(lst >= k)
            {
                int cnt = lst / k;
                ans += cnt * a[i][0];
                int x = cnt * a[i][0];
                while(res.size() && a[res.back()][0] >= a[i][0]) res.pop_back();
                while(x < k && cnt && res.size())
                {
                    int y = res.back();
                    if(cnt >= a[y][1])
                    {
                        res.pop_back();
                        cnt -= a[y][1];
                    }
                    else a[y][1] -= cnt;
                }
                lst %= k;
            }
            // if(i == 1)
            // cout << ans << ' ' << sum << endl;
            sum = lst;
            if(sum > 0) j = i;
            else j = i - 1;
            // while(j >= 0 && a[j][1] <= 0) j --;
            if(i == 0 && sum > 0) ans += a[i][0];
            // if(i == 1)
            // cout << ans << ' ' << sum << endl;
        }

        cout << ans << endl;
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3548kb

input:

2
4 6
1 1 8
7 2 5
1 1 7
3 2 6
8 1200000
100000 1 100000
100000 1 12345
100000 2 100000
100000 2 12345
100000 1 100000
100000 1 12345
100000 2 100000
100000 2 12345

output:

24
100000

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 42ms
memory: 7724kb

input:

5501
8 104
5 2 3
6 2 4
5 2 3
6 2 9
8 2 4
2 1 3
7 2 4
8 2 8
1 290
3 1 1
12 12
6 1 2
1 2 2
1 1 2
1 2 4
6 1 1
1 2 5
6 1 4
4 1 4
6 2 4
6 2 5
4 2 5
4 1 4
5 334
1 1 4
1 2 3
4 2 1
5 1 1
2 1 2
13 218
5 2 3
5 1 4
1 2 1
1 2 5
3 2 2
1 1 3
4 2 2
1 2 5
2 2 1
2 1 5
3 2 1
5 2 1
1 1 4
10 260
7 2 1
5 1 1
5 2 4
6 1 6...

output:

9
1
23
4
5
7
1
3
9
6
1
10
4
9
17
6
4
1
8
5
5
7
1
3
23
6
3
3
2
2
2
3
8
1
5
6
9
11
147
7
10
2
7
7
8
6
5
5
1
7
3
5
10
7
7
10
8
1
4
2
3
9
1
5
2
9
1
6
7
7
6
10
18
8
10
4
10
9
2
8
3
5
9
3
6
5
3
2
6
1
3
2
2
1
6
9
6
3
4
8
9
9
2
6
1
2
6
7
5
2
5
21
8
1
2
3
4
9
3
4
6
5
9
6
1
7
3
7
3
2
2
8
7
3
5
9
7
10
7
3
2
4
...

result:

wrong answer 226th lines differ - expected: '92', found: '91'