oj.uz

Submission #1040526

# Submission time Handle Problem Language Result Execution time Memory
1040526 2024-08-01T06:53:05 Z 김은성(#10995) Tricks of the Trade (CEOI23_trade) C++17
5 / 100
 57 ms 28604 KB 
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <deque>
#include <queue>
using namespace std;
typedef long long ll;
const ll INF = 0x3fffffffffffffff;
ll c[250009], psum[250009], s[250009];
bool ch[250009];
ll profit(int l, int r, int k){
	vector<ll> temp;
	if(r-l+1 < k)
		return -INF;
	int i;
	ll ans = 0;
	ans = -psum[r] + psum[l-1] + s[l] + s[r];
	return ans;
}

ll profit_ch(int l, int r, int k){
	vector<ll> temp;
	if(r-l+1 < k)
		return -INF;
	int i;
	ll ans = 0;
	ans = -psum[r] + psum[l-1] + s[l] + s[r];
	ch[l] = ch[r] = 1;
	return ans;
}
int main(){
	int n, m, i, j;
	ll ans = -INF;
	scanf("%d %d", &n, &m);
	for(i=1; i<=n; i++){
		scanf("%lld", &c[i]);
		psum[i] = psum[i-1] + c[i];
	}
	for(i=1; i<=n; i++){
		scanf("%lld", &s[i]);
	}
	vector<pair<int, int> > crit;
	vector<int> st;
	for(i=1; i<=n; i++){
		if(!st.empty() && s[st.back()] <= s[i]){
			crit.push_back(make_pair(st.back(), i));
			st.pop_back();
		}
		if(!st.empty())
			crit.push_back(make_pair(st.back(), i));
		st.push_back(i);
	}
	for(i=1; i<=n-m+1; i++)
		crit.push_back(make_pair(i, i+m-1));
	for(i=1; i<=n; i++){
		crit.push_back(make_pair(1, i));
		crit.push_back(make_pair(i, n));
	}
	for(i=0; i<crit.size(); i++){
		ans = max(ans, profit(crit[i].first, crit[i].second, m));
	}
	for(i=0; i<crit.size(); i++){
		if(profit(crit[i].first, crit[i].second, m) == ans)
			profit_ch(crit[i].first, crit[i].second, m);
	}
	printf("%lld\n", ans);
	for(i=1; i<=n; i++){
		printf("%d", ch[i]);
	}
	return 0;
}

Compilation message

trade.cpp: In function 'll profit(int, int, int)':
trade.cpp:19:6: warning: unused variable 'i' [-Wunused-variable]
   19 |  int i;
      |      ^
trade.cpp: In function 'll profit_ch(int, int, int)':
trade.cpp:29:6: warning: unused variable 'i' [-Wunused-variable]
   29 |  int i;
      |      ^
trade.cpp: In function 'int main()':
trade.cpp:63:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for(i=0; i<crit.size(); i++){
      |           ~^~~~~~~~~~~~
trade.cpp:66:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  for(i=0; i<crit.size(); i++){
      |           ~^~~~~~~~~~~~
trade.cpp:36:15: warning: unused variable 'j' [-Wunused-variable]
   36 |  int n, m, i, j;
      |               ^
trade.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
trade.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%lld", &c[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
trade.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |   scanf("%lld", &s[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 42 ms 24944 KB Output is correct
3 Correct 57 ms 28604 KB Output is correct
4 Correct 49 ms 26808 KB Output is correct
5 Partially correct 57 ms 25112 KB Partially correct
6 Partially correct 49 ms 26556 KB Partially correct
7 Partially correct 47 ms 26820 KB Partially correct
8 Correct 50 ms 27436 KB Output is correct
9 Correct 43 ms 25784 KB Output is correct
10 Correct 54 ms 26300 KB Output is correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 42 ms 24944 KB Output is correct
3 Correct 57 ms 28604 KB Output is correct
4 Correct 49 ms 26808 KB Output is correct
5 Partially correct 57 ms 25112 KB Partially correct
6 Partially correct 49 ms 26556 KB Partially correct
7 Partially correct 47 ms 26820 KB Partially correct
8 Correct 50 ms 27436 KB Output is correct
9 Correct 43 ms 25784 KB Output is correct
10 Correct 54 ms 26300 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 41 ms 25276 KB Output is correct
13 Correct 51 ms 25532 KB Output is correct
14 Correct 48 ms 24768 KB Output is correct
15 Partially correct 48 ms 24496 KB Partially correct
16 Partially correct 48 ms 24508 KB Partially correct
17 Partially correct 54 ms 25528 KB Partially correct
18 Correct 48 ms 25016 KB Output is correct
19 Correct 51 ms 25484 KB Output is correct
20 Correct 47 ms 25020 KB Output is correct
21 Incorrect 1 ms 2396 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -