Submission #766393

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
766393	2023-06-25T15:35:21 Z	HoriaHaivas	Self Study (JOI22_ho_t2)	C++14	10 / 100	93 ms	11452 KB

Main

/*
    "TLE is like the wind, always by my side"
    - Yasuo - 2022 -
*/
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

int n,m,i,j,r,pas;
int a[300001];
int b[300001];

int courseneed(int val, int a, int b)
{
    int ans;
    ans=0;
    if (a*m<val)
    {
        ans+=m;
        val-=a*m;
        if (val%b==0)
            ans+=val/b;
        else
            ans+=val/b+1;
    }
    else
    {
        if (val%a==0)
            ans+=val/a;
        else
            ans+=val/a+1;
    }
    return ans;
}

bool possible(int minimum)
{
    int sum;
    sum=0;
    for (i=1;i<=n;i++)
    {
         sum+=courseneed(minimum,a[i],b[i]);
    }
    if (sum<=n*m)
        return 1;
    return 0;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (i=1;i<=n;i++)
    {
         cin >> a[i];
    }
    for (i=1;i<=n;i++)
    {
         cin >> b[i];
    }
    for (i=1;i<=n;i++)
    {
         a[i]=max(a[i],b[i]);
    }
    r=0;
    pas=(1<<30);
    while (pas)
    {
         if (possible(r+pas))
             r+=pas;
         pas=pas/2;
    }
    cout << r;
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	324 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	324 KB	Output is correct
10	Correct	2 ms	472 KB	Output is correct
11	Correct	86 ms	10744 KB	Output is correct
12	Correct	93 ms	10896 KB	Output is correct
13	Correct	78 ms	8792 KB	Output is correct
14	Correct	85 ms	8820 KB	Output is correct
15	Correct	1 ms	324 KB	Output is correct
16	Correct	85 ms	6092 KB	Output is correct
17	Correct	92 ms	11452 KB	Output is correct
18	Correct	90 ms	10956 KB	Output is correct

Subtask #2

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	324 KB	Output is correct
2	Correct	85 ms	6092 KB	Output is correct
3	Correct	92 ms	11452 KB	Output is correct
4	Correct	90 ms	10956 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Incorrect	0 ms	212 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	324 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	324 KB	Output is correct
10	Correct	2 ms	472 KB	Output is correct
11	Correct	86 ms	10744 KB	Output is correct
12	Correct	93 ms	10896 KB	Output is correct
13	Correct	78 ms	8792 KB	Output is correct
14	Correct	85 ms	8820 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Incorrect	0 ms	212 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #4

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Incorrect	0 ms	212 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #5

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	324 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	324 KB	Output is correct
10	Correct	2 ms	472 KB	Output is correct
11	Correct	86 ms	10744 KB	Output is correct
12	Correct	93 ms	10896 KB	Output is correct
13	Correct	78 ms	8792 KB	Output is correct
14	Correct	85 ms	8820 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Incorrect	0 ms	212 KB	Output isn't correct
19	Halted	0 ms	0 KB	-