QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#225699#7524. A Challenge For a Tourist123ivan456WA 1ms3500kbC++203.4kb2023-10-24 23:56:522023-10-24 23:56:52

Judging History

你现在查看的是最新测评结果

  • [2023-10-24 23:56:52]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3500kb
  • [2023-10-24 23:56:52]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS                                                                                                                            

#include <algorithm> 
#include <bitset> 
#include <cassert> 
#include <chrono> 
#include <ctime> 
#include <deque> 
#include <fstream> 
#include <functional> 
#include <initializer_list> 
#include <iomanip> 
#include <iostream> 
#include <map> 
#include <math.h> 
#include <queue> 
#include <random> 
#include <set> 
#include <stack> 
#include <stdexcept> 
#include <string> 
#include <unordered_map> 
#include <unordered_set> 
#include <vector> 

using namespace std;

#define ll long long 
#define ull unsigned long long 
#define ld long double 
#define sz(a) (int) a.size() 

const int inf = (int)1e9;
const ll linf = (ll)1e18;

const ll mod = 1e9 + 7;
const ld eps = (ld)1e-14;
int gcd(ll a, ll b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

struct event {
    int x, type;
};

int scanline(vector<pair<int, int>> segments) {
    vector<event> events;

    for (auto i : segments) {
        int l = i.first;
        int r = i.second;
        events.push_back({ l, 1 });
        events.push_back({ r, -1 });
    }

    sort(events.begin(), events.end(), [](event a, event b) {
        return (a.x < b.x || (a.x == b.x && a.type > b.type));
        });

    int cnt = 0, res = 0;

    for (event e : events) {
        cnt += e.type;
        res = max(res, cnt);
    }

    return res;
}


void solve() {
    ll non = 1e14;
    ll n, m; cin >> n >> m;
    vector<vector<pair<pair<int, int>, pair<int, ll>>>> deg(n);
    for (int i = 0; i < m; ++i) {
        int l, r;
        ll s;
        string o;
        cin >> l >> r >> o >> s;
        if (o == ">=") deg[r - 1].push_back({ {l - 1, r - 1}, {1, s} });
        else deg[r - 1].push_back({ {l - 1, r - 1}, {0, s} });
    }
    vector<vector<pair<ll, ll>>> dp(n, vector<pair<ll, ll>>(n, { non, -non }));
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            for (int h = 0; h < deg[j].size(); ++h) {
                int l = deg[j][h].first.first;
                int r = deg[j][h].first.second;
                if (i >= l - 1) {
                    int o = deg[j][h].second.first;
                    ll s = deg[j][h].second.second;
                    if (!(dp[i][l - 1].first == non && dp[i][l - 1].first == -non)) {
                        dp[i][j] = { min(dp[i][l - 1].first + s, dp[i][j].first) , max(dp[i][l - 1].first + s, dp[i][j].second) };
                    }

                }
                else if (i == l) {
                    int o = deg[j][h].second.first;
                    ll s = deg[j][h].second.second;
                    dp[i][j] = { min(s, dp[i][j].first) , max(s, dp[i][j].second) };
                }

            }
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int h = 0; h < deg[i].size(); ++h) {
            int l = deg[i][h].first.first;
            int r = deg[i][h].first.second;
            if (dp[l][r].first < dp[l][r].second) {
                cout << "No\n";
                return;
            }
        }
    }
    cout << "YES";
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	//freopen("test.in", "r", stdin); 
	//cout << fixed << setprecision(7); 

	int tet = 1;
	//cin >> tet; 
	while (tet--) {
		solve();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3500kb

input:

6 6
5 6 3
6 2 2
1 2 1
2 3 2
2 4 3
4 5 4
3
1 3 1
1 3 3
1 3 5

output:

No

result:

wrong output format Expected integer, but "No" found