oj.uz

Submission #71650

# Submission time Handle Problem Language Result Execution time Memory
71650 2018-08-25T09:46:47 Z Mamnoon_Siam Go (COCI18_go) C++17
100 / 100
 374 ms 173808 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<
	T,
	null_type,
	less<T>,
	rb_tree_tag,
	tree_order_statistics_node_update>;

// gives the number of keys with value strictly less than x
#define lesscount(x) order_of_key(x)
// gives the iterator to kth element (starting from 0)
#define kthiterator(x) find_by_order(x)

#define clock_starts() clock_t begin = clock()
#define clock_ends() clock_t end = clock()
#define print_running_time() double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC; \
printf("Elapsed Time : %.10f second(s)\n", elapsed_secs)
#define readfile(s) freopen(s, "r", stdin)
#define writefile(s) freopen(s, "w", stdout)
#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define cin_cout_is_cool ios_base::sync_with_stdio(false); cin.tie(NULL)
#define PrintBinary(n) cout << #n << " = " << bitset<64>(n) << endl
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'
#define cin(n) scanf("%d", &n)
#define popcount(x) __builtin_popcount((x))
#define popcountll(x) __builtin_popcountll((x))

inline int myrand(int l, int r) {
	int ret = rand(); ret <<= 15; ret ^= rand();
	if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
	return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
    return os<<"(" <<p.first<<", "<<p.second<<")"; }

typedef pair<int, int> ii;
template<typename T> using min_pq =
	priority_queue<T, vector<T>, greater<T> >;

template<typename T>T max(T a_,T b_,T c_) { return max(a_,max(b_,c_)); }
template<typename T>T min(T a_,T b_,T c_) { return min(a_,min(b_,c_)); }
template<typename T>T min(T a_,T b_,T c_, T d_) { return min(min(a_, b_),min(c_,d_)); }
template<typename T>T max(T a_,T b_,T c_, T d_) { return max(max(a_, b_),max(c_,d_)); }

//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};

template<typename T> inline T ceil(T num, T d)
{ return (T)(num/d) + (num%d>(T)0 ? (T)1 : (T)0); }
#define block_no(idx) 		(idx/BLOCK_SIZE)
#define block_starting(idx) (block_no(idx)*BLOCK_SIZE)
#define block_ending(idx) 	(min(n, block_no(idx)*BLOCK_SIZE+BLOCK_SIZE-1))
#define block_rank(idx) 	(idx%BLOCK_SIZE)
#define time kjndfbkfd

const int maxn = 105;

int n, k, m;
int a[maxn], b[maxn], t[maxn];
int dp[maxn][maxn][2005][2];

int get(int l, int r, int time, int tog) {
	if(time > 2000) return 0;
	if(l == 1 and r == m) return 0;
	int &ret = dp[l][r][time][tog];
	if(ret != -1) return ret;
	ret = 0;
	int cur = tog ? a[r] : a[l];
	if(l != 1) { // going left
		int newtime = time + abs(cur-a[l-1]);
		ret = max(ret, (t[l-1] >= newtime ? b[l-1] : 0)+
						get(l-1, r, newtime, 0));
	}
	if(r != m) { // going right
		int newtime = time + abs(cur-a[r+1]);
		ret = max(ret, (t[r+1] >= newtime ? b[r+1] : 0)+
						get(l, r+1, newtime, 1));
	}
	return ret;
}

int32_t main () {
	//readfile("input.in");
	//writefile("output.out");
	MEMSET(dp, -1);
	cin>>n>>k>>m;
	for(int i=1; i<=m; i++) {
		cin>>a[i]>>b[i]>>t[i];
	}
	int ret = 0;
	for(int i=1; i<=m; i++) {
		int newtime = 1 + abs(a[i]-k);
		int val = t[i] >= newtime ? b[i] : 0;
		ret = max(ret, val+get(i,i,newtime,0));
	}
	cout<<ret<<endl;
	return 0;
}

Compilation message

go.cpp: In function 'int myrand(int, int)':
go.cpp:42:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
  ^~
go.cpp:42:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
                          ^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 173304 KB Output is correct
2 Correct 126 ms 173512 KB Output is correct
3 Correct 126 ms 173528 KB Output is correct
4 Correct 130 ms 173528 KB Output is correct
5 Correct 175 ms 173632 KB Output is correct
6 Correct 176 ms 173808 KB Output is correct
7 Correct 258 ms 173808 KB Output is correct
8 Correct 303 ms 173808 KB Output is correct
9 Correct 355 ms 173808 KB Output is correct
10 Correct 374 ms 173808 KB Output is correct