Edited by author 10.08.2025 21:25

How can I improve memory usage in this code?

#include "bits/stdc++.h"

using namespace std;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    short n;
    cin >> n;

    vector<pair<int,short>> s(n, pair<int,int>());

    for (int i = 0; i < n; i ++) {
        cin >> s[i].first;
        s[i].second = i;
    }

    sort(begin(s),end(s));
    for (short i = 1; i < n; i ++) {
        if (s[i].first == s[i - 1].first) {
            s.erase(begin(s) + i);
            n --;
            i --;
        }
    }

    vector<vector<short>> dp(n + 1, vector<short>(n + 1, 0));

    for (short i = 1; i < n - 1; i ++) {
        short l = i - 1;
        short r = i + 1;
        while (0 <= l && r < n) {
            int dfl = s[i].first - s[l].first;
            int dfr = s[r].first - s[i].first;
            if (dfl == dfr) {
                dp[i][r] = dp[l][i] + 1;
                l --;
                r ++;
            } else if (dfl > dfr) {
                r ++;
            } else {
                l --;
            }
        }
    }

    if (1 == n) {
        cout << "1\n1\n";
    } else {
        short mx = -1;
        short di = 0;
        short dj = 0;

        for (int i = 0; i < n - 1; i ++) {
            for (int j = i + 1; j < n; j ++) {
                if (dp[i][j] >= mx) {
                    mx = dp[i][j];
                    di = i;
                    dj = j;
                }
            }
        }

        int df = s[dj].first - s[di].first;

        mx += 2;

        cout << mx << '\n';

        for (; -1 < di;) {
            cout << s[dj].second + 1 << ' ';
            dj = di;
            di = -1;
            for (short i = 0; i < dj; i ++) {
                if (s[dj].first - s[i].first == df) {
                    di = i;
                    break;
                }
            }
        }

        cout << s[dj].second + 1 << '\n';
    }
}

Could you please give any hints or tests?

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    long a = 1;
    long b = 1;
    long ans = 0;
    if(n == 1 || n == 2){
        ans = 1;
    }
    else {
        while (n - 2 > 0){
            ans = a + b;
            a = b;
            b = ans;
            n--;
        }
    }

    cout << 2 * ans;
    return 0;
}

If you have "Time limit exceeded", just use sys.stdin.read()... and it will put load on memory, as I suppose reading huge amount of data via input() takes forever.

Стал изучать программирование только для того, чтобы кекать с таких заданий

N = int(input())
p = []
maxi = 0

for i in range(N):
    p.append(int(input()))

summi = sum(p)
for i in range(N):
  fsummi = sum(p[i:len(p)-i-1])
  if fsummi > maxi and fsummi>summi :
      maxi = fsummi

maxi2 = 0
for i in range(0, N-1):
  nsummi = sum(p[i::])
  jsummi=summi-nsummi
  if nsummi > jsummi:
    maxi2 = nsummi
  else:
    maxi2 = jsummi

if maxi>maxi2:
  print(maxi)
elif summi> maxi and summi>maxi2:
  print(summi)
else:
  print(maxi2)

Вобщем безнадега какая-то

Edited by author 25.04.2007 01:26

btw, random work, but that not just Monte-Carlo

Many people has already written about it, but... I really don't understand why I get WA. My program pass all tests here. Please, help to find bug.
--

Edited by author 29.07.2016 15:52

0 0
10 0
10 10
0 10
10 10 11
0 -10

Ans: 11.3731475899

0 0
10 0
10 10
0 10
10 10 10
-10 -10

Ans: 22.3606797750

Edited by author 23.10.2024 20:18

I used dp[901][8101] for dynamic programming,but I got TLE.Can anyone give me some hints?

Edited by author 22.10.2024 17:34

Post the code for this task, or what is wrong in my code?
import math
from decimal import Decimal, getcontext, ROUND_CEILING

getcontext().prec = 210

for _ in range(int(input())):
    H, l, h = map(int, input().split())
    H = Decimal(str(H))
    l = Decimal(str(l))
    h = Decimal(str(h))
    a = Decimal(str(math.sin(math.atan(H / l))))
    d = Decimal("4") * h * a
    g = Decimal(((H * H) + (l * l)) ** Decimal("0.5"))
    lm = Decimal("0")
    rm = Decimal("1e200")
    for i in range(700):
        mid = (lm + rm) / Decimal("2")
        if (d * (mid + 1) * mid) <= g:
            lm = mid
        else:
            rm = mid
    print(rm.quantize(Decimal('1'), rounding=ROUND_CEILING))

Edited by author 20.10.2024 02:41

In the statement, "any symbol" means NOT any valid ASCII char, but any byte, including those with codes 128..255. Common methods to read text in Rust, including stdin().read_line, expect valid UTF-8 and therefore crash on test 2 where bytes 128..255 are present. I got AC with this:

let mut reader = BufReader::new(stdin());
let mut s = Vec::new();
reader.read_until(10, &mut s).unwrap();

Nevermind. Solved.

I've detected my error with this input:

11 10
1 2
1 3
2 4
2 5
3 6
3 7
4 8
5 9
6 10
7 11

5 roads can be blocked.

Edited by author 29.08.2011 22:33

Wrong answer, test 30. Don't now what to do

WA 15: "Teams are as close in their sizes as possible." It doesn't mean that the size of one of the commands must be exactly n//2.
Wa 25: "Every team has at least one member"

Edited by author 15.10.2024 20:07

use dynamic programming by subsets, one mask in DP state for one breath in a row and two masks in DP state for two breaths in a row, time complexity ~O(k * (n+m)^2 * 4^(n+m))