oj.uz

Submission #1040513

# Submission time Handle Problem Language Result Execution time Memory
1040513 2024-08-01T06:44:26 Z 김은성(#10995) Tricks of the Trade (CEOI23_trade) C++17
0 / 100
 8000 ms 23124 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], 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;
	vector<ll> p;
	for(i=l; i<=r; i++){
		ans -= c[i];
		p.push_back(s[i]);
	}
	sort(p.begin(), p.end(), [](ll &u, ll &v){return u>v;});
	for(i=0; i<k; i++)
		ans += p[i];
	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;
	vector<pair<ll, int> > p;
	for(i=l; i<=r; i++){
		ans -= c[i];
		p.push_back(make_pair(-s[i], i));
	}
	sort(p.begin(), p.end());
	for(i=0; i<p.size(); i++){
		if(-p[i].first >= -p[k-1].first)
			ch[p[i].second] = 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]);
	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_ch(int, int, int)':
trade.cpp:44:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(i=0; i<p.size(); i++){
      |           ~^~~~~~~~~
trade.cpp: In function 'int main()':
trade.cpp:75: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]
   75 |  for(i=0; i<crit.size(); i++){
      |           ~^~~~~~~~~~~~
trade.cpp:78: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]
   78 |  for(i=0; i<crit.size(); i++){
      |           ~^~~~~~~~~~~~
trade.cpp:51:15: warning: unused variable 'j' [-Wunused-variable]
   51 |  int n, m, i, j;
      |               ^
trade.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
trade.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%lld", &c[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
trade.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%lld", &s[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct

Subtask #1
0.0 / 10.0

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

Subtask #2
0.0 / 10.0

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

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Execution timed out 8077 ms 23124 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Execution timed out 8077 ms 23124 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

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