Messages posted by: VlatkoSh

Dobro, go zameniv so for loop i ne pagja na vreme. Nikogas ne sum imal slicen problem, pa sum zaboravil na toj trik... Inaku na drug test kejs printa 99968567178 koga tocniot odgovor e 99880067892, znaci najverojatno gresno mi e resenieto. Fala za pomosta

Zadaca: https://codeforces.com/contest/954/problem/E
Submisija: https://codeforces.com/contest/954/submission/46753528

Ne razbiram zosto pagja na vreme. Zarem ne e O(n*log2(sum a))? Toa e najvekje 200000*log2(200000*1000000) < 8000000 operacii.

http://mendo.mk/Task.do?id=508

Ne razbiram zosto e gresen kodov.

dp[s][k][i] e maksimalniot broj na topki sto moze da se fatat ako sme vo s-tata sekunda, mozeme da se dvizime uste k pati i vo ovaa sekunda sme na i-tata pozicija.

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
template <class Key, class Compare = less<Key>> // find_by_order, order_of_key
using Tree = tree<Key, null_type, Compare, rb_tree_tag, tree_order_statistics_node_update>;

int N, K, S;
int t[1001];
int dp[1001][1001][11];

void _SOLVE_() {
  int T;
  cin >> T;
  while (T--) {
    cin >> N >> K >> S;
    for (int i = 1; i <= S; ++i)
      cin >> t[i];
    memset(dp, -1, sizeof(dp));
    dp[0][K][1] = 0;
    for (int s = 1; s <= S; ++s) {
      for (int k = 0; k <= K; ++k) {
        for (int i = 1; i <= N; ++i) {
          dp[s][k][i] = dp[s-1][k][i]; //ako prethodnata sekunda stoevme ovde
          if (k > 0 && k < K) {
            if (i > 1)
              dp[s][k][i] = max(dp[s][k][i], dp[s-1][k+1][i-1]); //ako prethodnata sekunda bevme edna pozicija levo od ovde
            if (i < N)
              dp[s][k][i] = max(dp[s][k][i], dp[s-1][k+1][i+1]); //ako prethodnata sekunda bevme edna pocizija desno od ovde
          }
          if (dp[s][k][i] != -1 && t[s] == i) //mozno e da sme ovde i topkata vo ovaa sekunda pagja kade sto sme
            dp[s][k][i] += 1;
        }
      }
    }
    int ans = 0;
    for (int k = 0; k <= K; ++k)
      for (int i = 1; i <= N; ++i)
        ans = max(ans, dp[S][k][i]);
    cout << ans << endl;
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  #ifdef _DEBUG
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
  #endif
  _SOLVE_();
}

EDIT
Go smeniv redot (k > 0 && k < K) i tocno e sega.

Mislam deka odgovoruvas na gresniot covek

Dali go citas errorot?
Eve primer za mapa: http://www.cplusplus.com/reference/map/map/operator[]/
Ti vo svojot kod pravis array so ns+1 mapi. Imas napisano mapa[S]=idx kade S e string sto ne e mozno, bidejki mapa vo tvojot kod e array i mozes samo so broevi da go ineksiras. Smeni go redot map<string,int> mapa[ns+1] vo map<string,int> mapa;.

Mislam deka implementirav se sto kaza, ama dava gresen rezultat. Veke mi se smaci od zadacava

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

void erase_single(multiset<int> &s, int x) {
  auto it = s.find(x);
  if (it != s.end()) s.erase(it);
}

int main() {

int s, m, a;
  int n, k;
  cin >> s >> m >> a >> n >> k;

vector<int> v(n);
  v[0] = s;
  for (int i = 1; i < n; ++i) {
    v[i] = (v[i-1] * m + a) % 65536;
  }

long long sum = 0;
  multiset<int> s1, s2;

sort(v.begin(), v.begin()+k);
  for (int i = 0; i < k; ++i) {
    if (i <= k/2 - !(k%2)) s1.insert(v[i]);
    else s2.insert(v[i]);
  }
  sum += v[k/2 - !(k%2)];

for (int i = k; i < n; ++i) {
    if (s1.count(v[i-k])) erase_single(s1, v[i-k]);
    else erase_single(s2, v[i-k]);
    s2.insert(v[i]);

while (!s1.empty() && !s2.empty() && *s1.rbegin() > *s2.begin()) {
      int x = *s1.rbegin();
      int y = *s2.begin();
      erase_single(s1, x);
      erase_single(s2, y);
      s1.insert(y);
      s2.insert(x);
    }
    while (s1.size() + 1 <= s2.size()) {
      int x = *s2.begin();
      erase_single(s2, x);
      s1.insert(x);
    }
    while (s1.size() > s2.size() + 1) {
      int x = *s1.rbegin();
      erase_single(s1, x);
      s2.insert(x);
    }
  }

cout << sum << endl;
}

Ako direktno go pratis resenieto na mendo, da.

Ako si na regionalen ili slicno treba na kompjuterot tamu, koga ke odis vo Compiler Settings na CodeBlocks, "Have g++ follow the C++11 ..." da bide stiklirano za da moze da gi koristis. Znaci ako go stikliras ova ke mozes na samiot kompjuter da gi koristis. Ama ako gi pratis direktno na mendo ke nema error kako i da e.

A kako da znaeme kade da go insertneme noviot element (v[i])? I dali prvo da se brise stariot (v[i-k]) element pa da se insertne noviot, ili prvo da se insertne noviot pa da se izbrise stariot?

Probuvam da ja resam ama ne mozam... bi te razbral ako go napises kodot?

Ne razbiram kako da se znae dali vo edniot ili vo drugiot heap da se stavi? I kako treba da se implementira heap?

http://mendo.mk/algoritmi/Task.do?competition=150&id=673

Ja resiv so slednoto:

Ama 100000% sum siguren deka ne e vaka nameneta da se resi...

Kako e nameneta da se resi?

Ok ja resiv taka... thanks a lot

Не очекував да биде меморискиот лимит... инаку дали решението ми е на прав пат или треба нешто попаметно? Пробав да ги правам броевите мод 60000011 ама има колизии.

Link: http://mendo.mk/Task.do?id=200

Ne razbiram zosto kodov mi dava Runtime Error za 5/10 testovi? Duri i simnav eden od niv i nemase Runtime Error kaj mene, tuku tocen odgovor.

Eve i eden od tie test kejsovi: https://pastebin.com/3ebnGE0f (output treba da e 13)

http://mendo.mk/Task.do?id=197
Ne razbiram zosto greedy delot e sekogas tocen? (oficijalno resenie, kako sto znam i edinstveno)

Edno od resenijata e so dinamicko programiranje. Ako ne znaes sto e, ti preporacuvam da go pobaras na internet za tutoriali. Ili pak mozes da go poglednes tutorialot na samava stranica (http://mendo.mk/Training.do?cid=6).

Inaku, eve go moeto resenie (verojano moze da se formulira poubavo, i da nema mnogu kejsovi, ama ne znam kako)
(K e brojot na ciklusi, N e brojot na clenovi vo komisijata)
Neka ciklus[i] e brojot na zadaci vo i-tiot ciklus (i∈[0, K-1])
Neka dp[i][j][m] e odgovorot na zadacata ako gi smetame samo prvite i ciklusi (ciklusite 0, 1, ..., i), prvite j clenovi na komisjata, i j-tiot clen ima vkupno m zadaci za pregleduvanje. Togas:

Vsusnost, pretposledniot kejs kazuva deka ako j-tiot clen ima 0 zadaci, mora barem eden ciklus da zeme (spored zadacata, sekoj mora barem eden).
Pretposledniot kejs simbolizira: ili go dodavame ovoj ciklus do segasniot (j-tiot) clen na komisijata i prodolzuvame so segasniot clen, ili go davame na sledniot (j+1-tiot) i prodolzuvame so nego.

Postoi i polesno resenie (vidi dolu)