Submission #46683

#	Time	Username	Problem	Language	Result	Execution time	Memory
46683		maksim_gaponov	Semiexpress (JOI17_semiexpress)	C++14	18 / 100	79 ms	760 KiB

semiexpress

#define _CRT_SECURE_NO_WARNINGS
#ifdef KEK
#define FILE_IN "input.txt"
#define FILE_OUT "output.txt"
#endif
#include <iostream>
#include <cstdlib>
#include <climits>
#include <set>
#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long ll;

void openFiles() {
#ifdef KEK
	assert(freopen(FILE_IN, "r", stdin));
	assert(freopen(FILE_OUT, "w", stdout));
#endif
}

const int MAXN = 310;
vector<pair<int, ll>> g[MAXN];
bool not_can[MAXN];
set<int> good;
ll dist[MAXN];
ll t;

void update(int u) {
    for (auto v : g[u]) {
        dist[v.first] = min(dist[v.first], dist[u] + v.second);
    }
}

int main() {
	openFiles();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    ll a, b, c;
    cin >> a >> b >> c;
    cin >> t;
    for (int i = 0; i < n - 1; i++) {
        g[i].push_back({i + 1, a});
    }
    int last = 0;
    for (int i = 0; i < m; i++) {
        int s;
        cin >> s;
        s--;
        good.insert(s);
        not_can[s] = true;
        if (last != s) {
            g[last].push_back({s, (s - last) * b});
            last = s;
        }
    }
    /*
    for (int i = 0; i < n; i++) {
        for (auto j : g[i]) {
            cout << i + 1 << " -> " << j.first + 1 << "; cost=" << j.second << "\n";
        }
    }
    */
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (not_can[i])
            continue;
        for (int j = i + 1; j < n; j++) {
            if (not_can[j])
                continue;
            //cout << i << " " << j << " check\n";
            int v1 = *prev(good.lower_bound(i), 1);
            g[v1].push_back({i, (i - v1) * c});
            //cout << "add edge " << v1 << " -> " << i << " cost=" << (i - v1) * c << "\n";
            good.insert(i);
            int v2 = *prev(good.lower_bound(j), 1);
            g[v2].push_back({j, (j - v2) * c});
            //cout << "add edge " << v2 << " -> " << j << " cost=" << (j - v2) * c << "\n";
            good.insert(j);
            for (int h = 1; h < n; h++) {
                dist[h] = 2 * t;
            }
            for (int h = 0; h < n; h++) {
                update(h);
            }
            int new_ans = 0;
            for (int h = 1; h < n; h++) {
                if (dist[h] <= t) {
                    new_ans++;
                }
                //cout << dist[h] << " ";
            }
            //cout << " & " << new_ans << "\n";;
            ans = max(ans, new_ans);
            g[v1].pop_back();
            g[v2].pop_back();
            good.erase(i);
            good.erase(j);
        }
    }
    cout << ans;
	return 0;
}

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