Niestety, nie byliśmy w stanie w pełni poprawnie wyświetlić tego pliku, ponieważ nie jest zakodowany w UTF-8.
Możesz pobrać ten plik i spróbować otworzyć go samodzielnie.
#include<cstdio> //#include<iostream> #include<algorithm> #include<vector> using namespace std; const int MAX = 500010; int n, m, a[MAX]; long long int sumy[MAX], b[MAX], d[MAX]; vector <pair<int, int> > licz; int punkt_podz (int pocz, int kon, int dni, long long int przyr) { // wynik, to pierwszy, kt�ry si� �apie w koszenie //cout << pocz << " " << kon << " " << dni << " " << przyr << endl; int sr, l = przyr / dni; while (pocz < kon) { sr = (pocz + kon)/2; if (a[sr] <= l) pocz = sr + 1; else kon = sr; } return pocz; } int main() { scanf("%d", &n); scanf("%d", &m); a[0] = 0; sumy[0] = 0; for (int i = 1; i <= n; i++) scanf("%d", &a[i]); sort (a, a + n + 1); for (int i = 1; i <=n; i++) sumy[i] = sumy[i - 1] + a[i]; licz.push_back(make_pair(n, 0)); int s = 1, j = 1; b[0] = 0; d[0] = 0; for (int i = 1; i <= m; i++) { unsigned long long int suma = 0; bool czy = true; scanf("%lld", &d[i]); scanf("%lld", &b[i]); //cout << "Zaczynamy " << i << endl; //cout << d[i] << " " << b[i] << endl; for (j = s - 1; j >= 0; j--) { int ost = licz[j].second, pocz, podz; if (j != 0) pocz = licz[j - 1].first + 1; else pocz = 1; int kon = licz[j].first; //cout << pocz << " " << kon << " " << ost << endl; // 2. Nawet nie zacz�o if (a[kon] * (d[i] - d[ost]) + b[ost] < b[i]) { //cout << "Jestem - nawet nie" << endl; if (suma != 0) { s = j + 2; if (j + 1 < licz.size()) licz[j + 1] = make_pair(n, i); else licz.push_back(make_pair(n, i)); } break; } // 1. Podzia� w �rodku lub wszystko //cout << "Jestem - podzial lub wszystko" << endl; if (a[pocz] * (d[i] - d[ost]) + b[ost] < b[i]) { //cout << "Jestem - podzial" << endl; czy = false; //cout << d[i] << " " << d[ost] << endl; podz = punkt_podz(pocz, kon, d[i] - d[ost], b[i] - b[ost]); pocz = podz; } //cout << sumy[kon] - sumy[pocz - 1] << " " << d[i] - d[ost] << endl; suma += (sumy[kon] - sumy[pocz - 1]) * (d[i] - d[ost]) + (kon - pocz + 1) * (b[ost] - b[i]); if (!czy) { s = j + 2; if (j + 1 < licz.size()) licz[j + 1] = make_pair(n, i); else licz.push_back(make_pair(n, i)); licz[j] = make_pair(podz - 1, ost); //cout << licz[s - 1].second << endl; break; } if (j == 0 && czy) { s = 1; licz[0] = make_pair(n, i); } } printf("%lld \n", suma); } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 | #include<cstdio> //#include<iostream> #include<algorithm> #include<vector> using namespace std; const int MAX = 500010; int n, m, a[MAX]; long long int sumy[MAX], b[MAX], d[MAX]; vector <pair<int, int> > licz; int punkt_podz (int pocz, int kon, int dni, long long int przyr) { // wynik, to pierwszy, kt�ry si� �apie w koszenie //cout << pocz << " " << kon << " " << dni << " " << przyr << endl; int sr, l = przyr / dni; while (pocz < kon) { sr = (pocz + kon)/2; if (a[sr] <= l) pocz = sr + 1; else kon = sr; } return pocz; } int main() { scanf("%d", &n); scanf("%d", &m); a[0] = 0; sumy[0] = 0; for (int i = 1; i <= n; i++) scanf("%d", &a[i]); sort (a, a + n + 1); for (int i = 1; i <=n; i++) sumy[i] = sumy[i - 1] + a[i]; licz.push_back(make_pair(n, 0)); int s = 1, j = 1; b[0] = 0; d[0] = 0; for (int i = 1; i <= m; i++) { unsigned long long int suma = 0; bool czy = true; scanf("%lld", &d[i]); scanf("%lld", &b[i]); //cout << "Zaczynamy " << i << endl; //cout << d[i] << " " << b[i] << endl; for (j = s - 1; j >= 0; j--) { int ost = licz[j].second, pocz, podz; if (j != 0) pocz = licz[j - 1].first + 1; else pocz = 1; int kon = licz[j].first; //cout << pocz << " " << kon << " " << ost << endl; // 2. Nawet nie zacz�o if (a[kon] * (d[i] - d[ost]) + b[ost] < b[i]) { //cout << "Jestem - nawet nie" << endl; if (suma != 0) { s = j + 2; if (j + 1 < licz.size()) licz[j + 1] = make_pair(n, i); else licz.push_back(make_pair(n, i)); } break; } // 1. Podzia� w �rodku lub wszystko //cout << "Jestem - podzial lub wszystko" << endl; if (a[pocz] * (d[i] - d[ost]) + b[ost] < b[i]) { //cout << "Jestem - podzial" << endl; czy = false; //cout << d[i] << " " << d[ost] << endl; podz = punkt_podz(pocz, kon, d[i] - d[ost], b[i] - b[ost]); pocz = podz; } //cout << sumy[kon] - sumy[pocz - 1] << " " << d[i] - d[ost] << endl; suma += (sumy[kon] - sumy[pocz - 1]) * (d[i] - d[ost]) + (kon - pocz + 1) * (b[ost] - b[i]); if (!czy) { s = j + 2; if (j + 1 < licz.size()) licz[j + 1] = make_pair(n, i); else licz.push_back(make_pair(n, i)); licz[j] = make_pair(podz - 1, ost); //cout << licz[s - 1].second << endl; break; } if (j == 0 && czy) { s = 1; licz[0] = make_pair(n, i); } } printf("%lld \n", suma); } return 0; } |