QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#225699 | #7524. A Challenge For a Tourist | 123ivan456 | WA | 1ms | 3500kb | C++20 | 3.4kb | 2023-10-24 23:56:52 | 2023-10-24 23:56:52 |
Judging History
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