oj.uz

Submission #1033884

# Submission time Handle Problem Language Result Execution time Memory
1033884 2024-07-25T07:28:16 Z vannnnnnnn Bigger segments (IZhO19_segments) C++14
0 / 100
 0 ms 348 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;

int main()
{
	ll n;
	scanf("%lld", &n);
	ll a[n+5];
	pair<ll, ll>dp[n+5];
	memset(dp, 0, sizeof(dp));
	for(int i=1; i<=n; i++)
	{
		scanf("%lld", &a[i]);
	}
	int p=2, last=2;
	dp[1].fi=a[1];
	dp[1].se=1;
	for(int i=2; i<=n; i++)
	{
		if(dp[p].fi==0)dp[p].se=i;
		dp[p].fi+=a[i];
//		printf("%lld %lld\n", dp[p].fi, dp[p-1].fi);
		if(dp[p].fi>=dp[p-1].fi)
		{
			while(dp[p-1].fi+a[dp[p].se]<=dp[p].fi-a[dp[p].se])
			{
				dp[p].fi-=a[dp[p].se];
				dp[p-1].fi+=a[dp[p].se];
				dp[p].se++;
			}
			p++;
		}
	}
	printf("%lld\n", p-1);
}

Compilation message

segments.cpp: In function 'int main()':
segments.cpp:13:26: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'struct std::pair<long long int, long long int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
   13 |  memset(dp, 0, sizeof(dp));
      |                          ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from segments.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, long long int>' declared here
  211 |     struct pair
      |            ^~~~
segments.cpp:37:13: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
   37 |  printf("%lld\n", p-1);
      |          ~~~^     ~~~
      |             |      |
      |             |      int
      |             long long int
      |          %d
segments.cpp:18:11: warning: unused variable 'last' [-Wunused-variable]
   18 |  int p=2, last=2;
      |           ^~~~
segments.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  scanf("%lld", &n);
      |  ~~~~~^~~~~~~~~~~~
segments.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |   scanf("%lld", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -