Program A, with global variables x
and y
:
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 3000000 + 10;
int dp[maxn], n, maxy;
int x, y; // <-- Global variables `x` and `y`
vector<int> a[maxn];
int main() {
freopen("demo.txt", "r", stdin);
freopen("demo.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
//int x, y;
scanf("%d %d", &x, &y);
a[y].push_back(x-1);
maxy = max(maxy, y);
}
for (int i = 1; i <= maxy; i++) {
dp[i] = dp[i - 1];
if (a[i].size() == 0) continue;
for (int j = 0; j < a[i].size(); j++) {
int u = a[i][j];
dp[i] = max(dp[i], dp[u] + i - u);
}
}
printf("%dn", dp[maxy]);
return 0;
}
Program B, almost the same with program A, but with local variables x
and y
(x
and y
can be considered as the two endpoints of an interval that $x < y$).
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 3000000 + 10;
int dp[maxn], n, maxy;
//int x, y;
vector<int> a[maxn];
int main() {
freopen("demo.txt", "r", stdin);
freopen("demo2.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x, y; // <-- Local variables `x` and `y`
scanf("%d %d", &x, &y);
a[y].push_back(x-1);
maxy = max(maxy, y);
}
for (int i = 1; i <= maxy; i++) {
dp[i] = dp[i - 1];
if (a[i].size() == 0) continue;
for (int j = 0; j < a[i].size(); j++) {
int u = a[i][j];
dp[i] = max(dp[i], dp[u] + i - u);
}
}
printf("%dn", dp[maxy]);
return 0;
}
Compile instruction (with -O2 optimized):
g++ demo.cpp -o demo -O2 -std=c++14
Compile information:
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=C:/mingw64/bin/../libexec/gcc/x86_64-w64-mingw32/8.1.0/lto-wrapper.exe
Target: x86_64-w64-mingw32
Thread model: posix
gcc version 8.1.0 (x86_64-posix-seh-rev0, Built by MinGW-W64 project)
Those two programs get the different results with the same input!
With the same input data, I’ve watched the variables of x
, y
, maxy
, a[i]
, and all of them got the same data. And the array element dp[i]
got the different data. I don’t know why, the variable dp[i]
and x
, y
are unrelated!
The big input data comes here: https://ww0.lanzouq.com/iesib26alt6f
It’s a txt
file, with about 150001 lines.
BTW:
This program is a solution to this question, However, you can ignore this information. The issue I’ve gotten seems to be no relation with that question.