oj.uz

Submission #493159

# Submission time Handle Problem Language Result Execution time Memory
493159 2021-12-10T07:40:46 Z Koying Semiexpress (JOI17_semiexpress) C++14
18 / 100
 606 ms 456 KB 
#pragma region
#pragma optimize("O3")
#include <bits/stdc++.h>
#define Weakoying ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define int long long
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int>>
#define pqueue priority_queue
#define pb push_back
#define F first
#define S second
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define cmax(a, b) a = (a > b ? a : b)
#define cmin(a, b) a = (a < b ? a : b)
#define put(x) cout << x << endl;
#define putarr(x) for(int i = 0; i < sizeof(x); i++) cout << x[i] << (" \n")[i == sizeof(x) - 1]; 
#define stop system("pause");
#define MEM(x, n) memset(x, n, sizeof(x));
#define lowbit(x) x &(-x)
#if !LOCAL
#define endl "\n"
#endif
const int INF = 0x3f3f3f3f;
const int P = 1e9+7;

using namespace std;
#pragma endregion
/******************************************************************************/
#define MAXN 100005
#define MAXM 3005
int n, m, k, t;
int A, B, C;
int x[MAXM];
pii dis[MAXM];

void find_dist()
{
	for(int i = 0; i < MAXM; i++)
		dis[i] = {INF, INF};
	dis[1] = {0, 0};
	for(int i = 1; i < m; i++)
	{
		dis[x[i]].F = B * (x[i] - 1);
		dis[x[i]].S = 0;
	}
	for(int i = 2; i <= n; i++)
	{
		cmin(dis[i].F, A * (i - 1));
		int F = upper_bound(x, x + m, i) - x;
		F--;
		if(F == -1) continue;
		cmin(dis[i].F, dis[x[F]].F + A * (abs(x[F] - i)));
		cmin(dis[i].S, abs(x[F] - i));
	}
	// for(int i = 1; i <= n; i++)
		// cout << dis[i].F << " ";
	// cout << endl;
	// for(int i = 1; i <= n; i++)
		// cout << dis[i].S << " ";
	// cout << endl;
}

void sol()
{
	cin >> n >> m >> k;
	cin >> A >> B >> C;
	cin >> t;
	set<int> s;
	for(int i = 0; i < m; i++)
	{
		cin >> x[i];
	}
	find_dist();
	// int ans = 0;
	// for(int i = 2; i <= n; i++)
	// {
		// if(dis[i].F <= t) 
		// ans++;
	// }
	// // cout << ans << endl;
	// sort(dis + 1, dis + n + 1, greater<pii>());
	// for(int i = 1; dis[i].F > t && k > m && i <= n; i++)
	// {
		// // cout << dis[i].F << endl;
		// if(dis[i].F - dis[i].S * (A - C) <= t)
		// {
			// ans++;
			// k--;
		// }
	// }
	// cout << ans << endl;
	if(k - m == 2)
	{
		int ans = 0;
		for(int i = 2; i < n; i++)
		{
			int ouo = 0;
			// if(binary_search(x, x + m, i)) continue;
			for(int j = i + 1; j <= n; j++)
			{
				// if(binary_search(x, x + m, j)) continue;	
				int cnt = 0;			
				for(int k = 2; k <= n; k++)
				{
					int tmp = dis[k].F;
					int F = upper_bound(x, x + m, k) - x;
					F--;
					if(F >= 0)
					{
						cmin(tmp, A * (k - x[F]) + dis[x[F]].F);
					}
					
					if(upper_bound(x, x + m, i) - x - 1 != -1 && i <= k)
						cmin(tmp, A * (abs(k - i)) + C * abs(i - (x[upper_bound(x, x + m, i) - x - 1])) + dis[x[upper_bound(x, x + m, i) - x - 1]].F);
					if(upper_bound(x, x + m, j) - x - 1 != -1 && j <= k)
						cmin(tmp, A * (abs(k - j)) + C * abs(j - (x[upper_bound(x, x + m, j) - x - 1])) + dis[x[upper_bound(x, x + m, j) - x - 1]].F);
					
					if(tmp <= t)
						cnt++;
					// cout << tmp << " ";
				}
				// cout << endl;
				// if(cnt > ans)
					// cout << i << " " << j << endl;
				cmax(ans, cnt);
			}
			// cout << i << " " << ouo << endl;
		}
		cout << ans << endl;
	}
}

signed main()
{
    Weakoying;
    int t = 1;
    //while (cin >> t)
    {
    	while (t--)
        {
            sol();
        }
    }
        
    return 0;
}

Compilation message

semiexpress.cpp:1: warning: ignoring '#pragma region ' [-Wunknown-pragmas]
    1 | #pragma region
      | 
semiexpress.cpp:2: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    2 | #pragma optimize("O3")
      | 
semiexpress.cpp:29: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   29 | #pragma endregion
      | 
semiexpress.cpp: In function 'void sol()':
semiexpress.cpp:99:8: warning: unused variable 'ouo' [-Wunused-variable]
   99 |    int ouo = 0;
      |        ^~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 344 KB Output is correct
2 Correct 340 ms 340 KB Output is correct
3 Correct 606 ms 344 KB Output is correct
4 Correct 339 ms 340 KB Output is correct
5 Correct 328 ms 344 KB Output is correct
6 Correct 384 ms 344 KB Output is correct
7 Correct 339 ms 344 KB Output is correct
8 Correct 377 ms 456 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 344 KB Output is correct
2 Correct 340 ms 340 KB Output is correct
3 Correct 606 ms 344 KB Output is correct
4 Correct 339 ms 340 KB Output is correct
5 Correct 328 ms 344 KB Output is correct
6 Correct 384 ms 344 KB Output is correct
7 Correct 339 ms 344 KB Output is correct
8 Correct 377 ms 456 KB Output is correct
9 Incorrect 0 ms 332 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 344 KB Output is correct
2 Correct 340 ms 340 KB Output is correct
3 Correct 606 ms 344 KB Output is correct
4 Correct 339 ms 340 KB Output is correct
5 Correct 328 ms 344 KB Output is correct
6 Correct 384 ms 344 KB Output is correct
7 Correct 339 ms 344 KB Output is correct
8 Correct 377 ms 456 KB Output is correct
9 Incorrect 0 ms 332 KB Output isn't correct
10 Halted 0 ms 0 KB -