Submission #493139

#	Time	Username	Problem	Language	Result	Execution time	Memory
493139		Koying	Semiexpress (JOI17_semiexpress)	C++14	0 / 100	1 ms	332 KiB

semiexpress

#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()
{
	MEM(dis, 63);
	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;
		if(F != m)
		{
			cmin(dis[i].F, dis[x[F]].F + A * (abs(x[F] - i)));
			cmin(dis[i].S, abs(x[F] - i));
			
		}
		F--;
		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 = 1; k <= n; k++)
				// {
					// int tmp = 0;
					// int F = upper_bound(x, x + m, k) - x;
					// if(F != m)
						// cmin(tmp, B * (x[F] - k));
					// cmin(tmp, B * (k - x[F - 1]));
					// cmin(tmp, C * abs(k - i));
					// cmin(tmp, C * abs(k - j));
					// if(tmp <= t)
						// cnt++;
				// }
				// 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 (stderr)

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 find_dist()':
semiexpress.cpp:20:41: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'struct std::pair<long long int, long long int>' with no trivial copy-assignment [-Wclass-memaccess]
   20 | #define MEM(x, n) memset(x, n, sizeof(x));
      |                                         ^
semiexpress.cpp:40:2: note: in expansion of macro 'MEM'
   40 |  MEM(dis, 63);
      |  ^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from semiexpress.cpp:3:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, long long int>' declared here
  211 |     struct pair
      |            ^~~~

• Subtask 1: 0 / 18
• Subtask 2: 0 / 30
• Subtask 3: 0 / 52