oj.uz

답안 #1040533

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1040533 2024-08-01T06:59:11 Z 김은성(#10995) Tricks of the Trade (CEOI23_trade) C++17
5 / 100
 72 ms 42680 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);
	}
	st.clear();
	for(i=n; i>=1; i--){
		if(!st.empty() && s[st.back()] <= s[i]){
			crit.push_back(make_pair(i, st.back()));
			st.pop_back();
		}
		if(!st.empty())
			crit.push_back(make_pair(i, st.back()));
		st.push_back(i);
	}
	st.clear();
	for(i=n; i>=1; i--){
		if(!st.empty() && s[st.back()] < s[i]){
			crit.push_back(make_pair(i, st.back()));
			st.pop_back();
		}
		if(!st.empty())
			crit.push_back(make_pair(i, st.back()));
		st.push_back(i);
	}
	st.clear();
	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:93: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]
   93 |  for(i=0; i<crit.size(); i++){
      |           ~^~~~~~~~~~~~
trade.cpp:96: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]
   96 |  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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
5.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 57 ms 41436 KB Output is correct
3 Correct 62 ms 40552 KB Output is correct
4 Correct 61 ms 41392 KB Output is correct
5 Correct 72 ms 40884 KB Output is correct
6 Correct 62 ms 40116 KB Output is correct
7 Partially correct 61 ms 40896 KB Partially correct
8 Correct 61 ms 40888 KB Output is correct
9 Correct 56 ms 41624 KB Output is correct
10 Correct 58 ms 41908 KB Output is correct

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 57 ms 41436 KB Output is correct
3 Correct 62 ms 40552 KB Output is correct
4 Correct 61 ms 41392 KB Output is correct
5 Correct 72 ms 40884 KB Output is correct
6 Correct 62 ms 40116 KB Output is correct
7 Partially correct 61 ms 40896 KB Partially correct
8 Correct 61 ms 40888 KB Output is correct
9 Correct 56 ms 41624 KB Output is correct
10 Correct 58 ms 41908 KB Output is correct
11 Correct 0 ms 2392 KB Output is correct
12 Correct 57 ms 40548 KB Output is correct
13 Correct 61 ms 41140 KB Output is correct
14 Correct 60 ms 40372 KB Output is correct
15 Correct 68 ms 40884 KB Output is correct
16 Correct 64 ms 41908 KB Output is correct
17 Partially correct 64 ms 42680 KB Partially correct
18 Correct 61 ms 40372 KB Output is correct
19 Correct 63 ms 41652 KB Output is correct
20 Correct 69 ms 40376 KB Output is correct
21 Incorrect 0 ms 2396 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -