QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#407684#795. Cloud Computingsichengzhou#0 1ms3968kbC++142.2kb2024-05-09 09:05:072024-05-09 09:05:09

Judging History

This is the latest submission verdict.

  • [2024-05-09 09:05:09]
  • Judged
  • Verdict: 0
  • Time: 1ms
  • Memory: 3968kb
  • [2024-05-09 09:05:07]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 2020, M = 52;
bool fl = 1;
#define x first
#define y second
typedef long long LL;
typedef pair < bool, LL > pbL;
int n, m;
struct Node
{
  int c, f, v, type;
  bool operator < (const Node & t) const
  {
	return f < t.f;
  }
}
a[N + N], p1[N], p2[N];
int tot, s, s1;
pbL f[N * M], g[N + N];
int
main ()
{
  scanf ("%d", &n);
  for (int i = 1; i <= n; i++)
	{
	  tot++;
	  scanf ("%d%d%d", &a[tot].c, &a[tot].f, &a[tot].v);
	  a[tot].type = 1;
	  if (a[tot].v > 1)
		fl = 0;
	  s += a[tot].c;
	  p1[i] = a[tot];
	}
  scanf ("%d", &m);
  for (int i = 1; i <= m; i++)
	{
	  tot++;
	  scanf ("%d%d%d", &a[tot].c, &a[tot].f, &a[tot].v);
	  a[tot].type = 2;
	  if (a[tot].v > 1)
		fl = 0;
	  s1 += a[tot].c;
	  p2[i] = a[tot];
	}
  if (fl)
	{
	}
  sort (a + 1, a + tot + 1);
  sort (p1 + 1, p1 + tot + 1);
  sort (p2 + 1, p2 + tot + 1);
  f[0].x = 1;
  g[n].x = 1;
  if (fl == 0||1)
	{
	  for (int i = 1; i <= tot/2; i++)
		{
		  pbL cur;
		  if (a[i].type == 1)
			{
			  for (int j = 0; j <= s1; j++)
				{
				  cur = f[j];
				  cur.y -= a[i].v;
				  f[max (j - a[i].c, 0)] = max (f[max (j - a[i].c, 0)], cur);
				}
			}
		  else
			{
			  for (int j = s1 - a[i].c; j >= 0; j--)
				{
				  cur = f[j];
				  cur.y += a[i].v;
				  f[j + a[i].c] = max (f[j + a[i].c], cur);
				}
			}
		}
	  printf ("%lld\n", f[0].y);
	}
  else
	{
	  //   cout<<s1<<endl;
	  g[n].x = 1;
	  g[n].y = s1;
	  for (int i = 1; i <= tot; i++)
		{
		  pbL cur;
		  if (a[i].type == 1)
			{
			  for (int j = 1; j <= n + m; j++)
				{
				  cur = g[j];
				  cur.y += a[i].c;
				  cur.y = min (cur.y, (LL) s1);
				  g[j - 1] = max (g[j - 1], cur);
				}
			}
		  else
			{
			  for (int j = n + m - 1; j >= 0; j--)
				{
				  cur = g[j];
				  cur.y -= a[i].c;
				  g[j + 1] = max (g[j + 1], cur);
				}
			}
		  /*    cout<<i<<endl;
		     for(int j=0;j<=n+m;j++)
		     {
		     cout<<g[j].x<<' '<<g[j].y<<endl;
		     } */
		}
	  for (int i = n + m; i >= n; i--)
		{
		  //    cout<<g[i].x<<' '<<g[i].y<<endl;
		  if (g[i].x == 1 && g[i].y == s1)
			{
			  printf ("%d\n", i - n);
			  break;
			}
		}
	}
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3920kb

input:

1
3 3253 744
1
1 2012 798

output:

0

result:

wrong answer 1st lines differ - expected: '54', found: '0'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #18:

score: 0
Wrong Answer
time: 1ms
memory: 3864kb

input:

12
1 3728 3883
1 2483 1377
1 2421 2213
1 4866 648
1 2292 1737
1 4027 657
1 2119 2801
1 2559 859
1 3859 3261
1 2908 3110
1 2917 2467
1 2011 3406
18
1 2558 4956
1 3468 2947
1 4577 4082
1 2886 2222
1 2979 3572
1 2266 4860
1 2868 3183
1 3665 4259
1 2607 4802
1 2811 3874
1 2314 4212
1 2638 3152
1 2944 44...

output:

11848

result:

wrong answer 1st lines differ - expected: '23934', found: '11848'

Subtask #4:

score: 0
Wrong Answer

Test #26:

score: 0
Wrong Answer
time: 1ms
memory: 3856kb

input:

10
2 1 2274
2 1 2524
1 1 2699
5 1 2930
4 1 1802
2 1 2734
4 1 1036
3 1 2741
5 1 1138
1 1 2132
6
5 1 3573
1 1 4847
2 1 3885
1 1 2183
2 1 2534
1 1 4659

output:

0

result:

wrong answer 1st lines differ - expected: '17705', found: '0'

Subtask #5:

score: 0
Wrong Answer

Test #34:

score: 18
Accepted
time: 1ms
memory: 3828kb

input:

4
43 2536 1
48 2001 1
49 3407 1
48 3778 1
2
42 3314 1
43 3073 1

output:

0

result:

ok single line: '0'

Test #35:

score: 18
Accepted
time: 1ms
memory: 3968kb

input:

57
47 1212 1
42 1104 1
48 1247 1
44 1420 1
41 1428 1
46 1364 1
47 1245 1
40 1199 1
48 1027 1
49 1113 1
50 1439 1
45 1208 1
41 1231 1
41 1131 1
48 1080 1
43 1218 1
45 1145 1
44 1071 1
43 1393 1
47 1314 1
45 1306 1
47 1439 1
42 1124 1
49 1383 1
47 1175 1
45 1099 1
46 1378 1
45 1285 1
46 1323 1
41 1234...

output:

0

result:

ok single line: '0'

Test #36:

score: 0
Wrong Answer
time: 1ms
memory: 3748kb

input:

570
46 5838 1
40 6425 1
44 5897 1
42 6694 1
49 4775 1
43 6145 1
49 3903 1
46 4661 1
50 5987 1
43 7469 1
40 8641 1
47 7424 1
43 6303 1
44 9446 1
42 9626 1
48 3201 1
46 4829 1
44 7695 1
41 8599 1
48 4502 1
43 7551 1
44 4095 1
50 7648 1
45 5950 1
50 8967 1
42 3801 1
45 4723 1
42 8216 1
47 9791 1
41 586...

output:

108

result:

wrong answer 1st lines differ - expected: '233', found: '108'

Subtask #6:

score: 0
Skipped

Dependency #1:

0%