akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <cmath>
#include <numeric>
using namespace std;

pair <long long, int> A_to_ind[100000];

int main(){
    int N;
    cin >> N;
    for(int i = 0; i < N; i++){
        long long A;
        cin >> A;
        A_to_ind[i] = make_pair(A, i);
    }

    int ans = 0;
    sort(A_to_ind, A_to_ind + N);
    for(int i = 0; i < N; i++){
        if(i % 2 != A_to_ind[i].second % 2){
            ans ++;
        }
    }
    cout << ans / 2 << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
using namespace std;

#define rep(i,n) for(int i=0; i<n; i++)
const int INF = 1000000;

enum {
    DIR_UP,
    DIR_LEFT,
    DIR_RIGHT,
    DIR_DOWN,
};

int main(){
    int w, h;
    while( cin >> w >> h, w||h ) {
        bool wall[30][30][4];
        int maze[30][30];
        rep(y,h)  rep(x,w)  maze[x][y] = INF;
        rep(i, 2*h-1) {
            if( i%2 ) {
                // 横壁
                int y = i/2;
                rep(x, w) {
                    int k;
                    cin >> k;
                    wall[x][y][DIR_DOWN] = (k==0);
                    wall[x][y+1][DIR_UP] = (k==0);
                }
            } else {
                // 縦壁
                int y = i/2;
                rep(x, w-1) {
                    int k;
                    cin >> k;
                    wall[x][y][DIR_RIGHT] = (k==0);
                    wall[x+1][y][DIR_LEFT] = (k==0);
                }
            }
        }
        // 外周
        rep(y, h) {
            wall[0][y][DIR_LEFT] = false;
            wall[w-1][y][DIR_RIGHT] = false;
        }
        rep(x, w) {
            wall[x][0][DIR_UP] = false;
            wall[x][h-1][DIR_DOWN] = false;
        }

        queue< pair<int,int> > que;
        que.push( make_pair<int,int>(0, 0) );
        maze[0][0] = 1;

        while( !que.empty() ) {
            int x = que.front().first;
            int y = que.front().second;
            if( x==w-1 && y==h-1 ) {
                break;
            }
            que.pop();
            if( wall[x][y][DIR_UP] && maze[x][y-1]>maze[x][y]+1 ) {
                maze[x][y-1] = maze[x][y] + 1;
                que.push( make_pair<int, int>(x, y-1) );
            }
            if( wall[x][y][DIR_LEFT] && maze[x-1][y]>maze[x][y]+1 ) {
                maze[x-1][y] = maze[x][y] + 1;
                que.push( make_pair<int, int>(x-1, y) );
            }
            if( wall[x][y][DIR_RIGHT] && maze[x+1][y]>maze[x][y]+1 ) {
                maze[x+1][y] = maze[x][y] + 1;
                que.push( make_pair<int, int>(x+1, y) );
            }
            if( wall[x][y][DIR_DOWN] && maze[x][y+1]>maze[x][y]+1 ) {
                maze[x][y+1] = maze[x][y] + 1;
                que.push( make_pair<int, int>(x, y+1) );
            }
        }
        if( maze[w-1][h-1] == INF ) maze[w-1][h-1] = 0;
        cout << maze[w-1][h-1] << endl;

    }
    return 0;
}

Measured memory_bytes: 1220
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define mod 1000000007
#define pb push_back
#define ff first
#define ss second
#define mp make_pair
#define all(x) x.begin(),x.end()
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
 




int main()
{
    fastio
    ll t,i,j,x=0;
    
    
    string a,b;
    cin>>a>>b;
    for(i=0;i<a.size();i++)
    {
        if(a[i]!=b[i])
        ++x;
    }
    cout<<x;
    
    
}


Measured memory_bytes: 3796
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <ctype.h>
#include <ios> 
#include <iomanip>
using namespace std;

#define N_MAX   (100000)
#define LL_MAX_NUM (1LL<<60)
#define INF 1e7

typedef long long ll;
typedef long long int lli;

int main() {
	string s; cin >> s;
    int ssize, ans, i, j;
    ssize = s.size();
    for (i = 0; i < ssize; i++)
    {
        if (s[i] == 'A')
        {
            break;
        }
    }
    for (j = ssize - 1; j >= 0; j--)
    {
        if (s[j] == 'Z')
        {
            break;
        }
    }
    ans = j - i + 1;
    cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>

const int maxn = 1e5 + 100;

int a[maxn], n;

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", a + i);
	}
	std::sort(a, a + n);
	if(a[0] == a[n - 1]) {
		if(a[n - 1] <= n / 2 || a[n - 1] == n - 1) {
			puts("Yes");
		}
		else {
			puts("No");
		}
	}
	else if(a[0] == a[n - 1] - 1) {
		for (int i = 0; i < n; ++i) {
			if(a[i] != a[0]) {
				if(a[n - 1] <= i + (n - i) / 2 && a[n - 1] >= i + 1) {
					puts("Yes");
				}
				else {
					puts("No");
				}
				break;
			}
		}
	}
	else {
		puts("No");
	}
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;

template <typename T>
T gcd(T a, T b)
{
	while (b)
	{
		T tmp = b;
		b = a % b;
		a = tmp;
	}
	return a;
}

int main()
{
	int64_t n, x;
	cin >> n >> x;
	vector<int64_t> as(n);
	for (auto &a : as)
	{
		cin >> a;
	}
	for (auto &a : as)
	{
		a = abs(x - a);
	}
	int64_t ans = as[0];
	for (int i = 1; i < n; i++)
	{
		ans = gcd(ans, as[i]);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
using namespace std;

int o[100];

int main() {
    int N,K;
    cin >> N >> K;
    int d;
    for(int i=0;i<K;i++){
        cin >> d;
        for(int j=0;j<d;j++){
            int a;
            cin >> a;
            o[a-1]++;
        }
    }
    int cnt = 0;
    for(int i=0;i<N;i++){
        if(o[i] == 0){
            cnt++;
        }
    }
    cout << cnt<< endl;

	return 0;
}

Measured memory_bytes: 3224
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using P = pair<int,int>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
const ll INF =1001001001001001001;

int main()
{
   ll n, x;
   cin >> n >> x;
   vector<ll>a(n);
   rep(i,n) cin >> a[i];
   ll ans = 0;

   rep(i,n-1)
   {
      if(x >= a[i] + a[i+1]) continue;
      if(x < a[i])
      {
         ans += a[i] - x + a[i+1];
         a[i] = x;
         a[i+1] = 0;
      }
      else if(x == a[i])
      {
         ans += a[i+1];
         a[i+1] = 0;
      }
      else
      {
         ll tmp = x -a[i];
         ans +=  a[i+1] - tmp;
         a[i+1] = tmp;
      }
   }
  // rep(i,n) cout << a[i] << " ";
   cout << endl;
  cout << ans << endl;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); ++i)
double const PI = 3.1415926535897932384626433;

int main() {
    int n;
    ll ans = 0;
    cin >> n;
    map<string, ll> a;
    rep(i, n) {
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        if (a[s] >= 1)
            ans += a[s];
        a[s]++;
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 11204
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <utility>
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

#define init() ios::sync_with_stdio(false); cin.tie();
#define for0(i, n) for (int i=0; i<n; i++)
#define for1(i, n) for (int i=1; i<=n; i++)
#define for2(i, a, b) for (int i=a; i<=b; i++)
#define bac0(i, n) for (int i=n-1; i>=0; i--)
#define bac1(i, n) for (int i=n; i>0; i--)
#define bac2(i, a, b) for (int i=a; i>=b; i--)
#define PB push_back
#define MOD 1000000009
#define S second
#define F first
#define B 99997LL

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, char> ic;

const int N = (int) (2e5 + 5);

ll n, ans;
ll a[N];

int main() {
    init()

    cin >> n;
    for1 (i, n) cin >> a[i], a[i] = a[i - 1] + a[i];
    sort(a + 1, a + n + 1);

    ll c = 1;
    for2 (i, 1, n) {
        if (i > 1) {
            if (a[i] == a[i - 1]) {
                c++;
            } else {
                ans += c * (c - 1) / 2;
                c = 1;
            }
        }
        if (a[i] == 0) ans++;
    }
    ans += c * (c - 1) / 2;

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1792
N = int(input())
l = list(range(1,N+1))
l_count = []
for e in l:
  count = 0
  while e % 2 == 0:
    e /= 2
    count += 1
  l_count.append(count)
max_index = l_count.index(max(l_count))
print(l[max_index])

Measured memory_bytes: 3060
k = gets.to_i

queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]

(1..k).each do |i|
  x = queue.shift
  print x if i == k
  shimohitoketa = x.modulo(10)
  middle = (10 * x) + shimohitoketa
  queue.push(middle - 1) if shimohitoketa != 0
  queue.push(middle)
  queue.push(middle + 1) if shimohitoketa != 9
end


Measured memory_bytes: 3964
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define sc(x) scanf("%d",&x);
int main(){
    int n, m, ans = 0;
    sc(n)
    string s;
    map<string, int> mp;
    for (int i = 0; i < n; i++){
        cin >> s;
        ++mp[s];
    }
    sc(m)
    for (int i = 0; i < m; i++){
        cin >> s;
        --mp[s];
    }
    for (const auto &x : mp){
        ans = max(ans, x.second);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	list := make([]int, m)
	for i := 0; i < m; i++ {
		fmt.Scan(&list[i])
	}

	if n >= m {
		fmt.Println(0)
	} else {
		sort.Sort(sort.Reverse(sort.IntSlice(list)))
		result := list[0] - list[m-1]
		list2 := make([]int, m-1)
		for i := 0; i < m-1; i++ {
			list2[i] = list[i] - list[i+1]
		}

		sort.Sort(sort.Reverse(sort.IntSlice(list2)))

		for i := 0; i < n-1; i++ {
			result -= list2[i]
		}
		fmt.Println(result)
	}
}


Measured memory_bytes: 5504
///AJoy Sarker ,CSE JAHANGIRNAGAR UNIVERSITY 48 Batch
#include<bits/stdc++.h>
using namespace std;
#define SORT(c) sort((c).begin(),(c).end());
#define inf INT_MAX/3
#define pb push_back
#define MP make_pair
#define pii pair<int,int>
#define pcc pair<char,char>
#define pic pair<int,char>
#define pci pair<char,int>
#define VS vector<string>
#define VI vector<int>
#define MIN(a,b) (a>b?b:a)
#define MAX(a,b) (a>b?a:b)
#define pi 3.141592653589793
#define in scanf
#define out printf
#define ll long long
#define ull unsigned long long
#define w(x) int x;cin>>x;while(x--)
#define fast ios_base::sync_with_stdio(0)
#define FOR(i,a,b) for( int i=(a),_b=(b);i<=_b;i++)
#define DOW(i,b,a) for( int i=(b),_a=(a);i>=_a;i--)
typedef unsigned long long UL;
template<typename T>inline T  S(T a)
{
    return a*a;
}
template<class T>inline string tostring(T a)
{
    ostringstream os("");
    os << a;
    return os.str();
}
template<typename T>inline ll tolong(T a)
{
    ll res;
    istringstream os(a);
    os>>res;
    return res;
}
template<typename T>inline T gcd(T a, T b)
{
    if (b == 0)return a;
    else return gcd(b, a % b);
}
template<typename T>inline T bigmod(T a, T b, T m)
{
    if (b == 0)return 1;
    else if (b % 2 == 0)return S(bigmod(a, b / 2, m)) % m;
    else return (a % m*bigmod(a, b - 1, m)) % m;
}
#define N 20000009
bool prime[N];
vector<ll> prm;
void seive ()
{

    memset(prime, true, sizeof(prime));

    for( ll i=2; i*i<=N; i++)
    {
        if (prime[i] == true)
        {
            prm.pb(i);
            for (ll j=i*i; j<=N; j += i)
                prime[j] = false;
        }
    }
}
void pr (int f)
{
    if(f==1)
        cout<<"Yes\n";
    else
        cout<<"No\n";
}
int main()
{
    fast;
    int x, a, b;
    string ans = "";
    cin >> x >> a >> b;
    if (b <= a)
    {
        ans = "delicious";
    }
    else if (b <= a + x)
    {
        ans = "safe";
    }
    else if (b > a + x)
    {
        ans = "dangerous";
    }
    cout << ans << endl;
    return 0;
}






Measured memory_bytes: 256
#![allow(unused_imports, unused_macros, dead_code)]

macro_rules! min {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        it.next().map(|z| it.fold(z, |x, y| min!(x, y)))
    }};
    ($x:expr) => ($x);
    ($x:expr, $($ys:expr),*) => {{
        let t = min!($($ys),*);
        if $x < t { $x } else { t }
    }}
}
macro_rules! max {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        it.next().map(|z| it.fold(z, |x, y| max!(x, y)))
    }};
    ($x:expr) => ($x);
    ($x:expr, $($ys:expr),*) => {{
        let t = max!($($ys),*);
        if $x > t { $x } else { t }
    }}
}
macro_rules! ewriteln {
    ($($args:expr),*) => { let _ = writeln!(&mut std::io::stderr(), $($args),*); };
}
macro_rules! trace {
    ($x:expr) => {
        #[cfg(debug_assertions)]
        eprintln!(">>> {} = {:?}", stringify!($x), $x)
    };
    ($($xs:expr),*) => { trace!(($($xs),*)) }
}
macro_rules! flush {
    () => {
        std::io::stdout().flush().unwrap();
    };
}
macro_rules! put {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        if let Some(x) = it.next() { print!("{}", x); }
        for x in it { print!(" {}", x); }
        println!("");
    }};
    ($x:expr) => { println!("{}", $x) };
    ($x:expr, $($xs:expr),*) => { print!("{} ", $x); put!($($xs),*) }
}

const M: i64 = 1_000_000_007;

fn main() {
    let mut sc = Scanner::new();
    let n: usize = sc.cin();
    for _ in 0..n {
        print!("ACL");
    }
    println!();
}

use std::collections::VecDeque;
use std::io::{self, Write};
use std::str::FromStr;

struct Scanner {
    stdin: io::Stdin,
    buffer: VecDeque<String>,
}
impl Scanner {
    fn new() -> Self {
        Scanner {
            stdin: io::stdin(),
            buffer: VecDeque::new(),
        }
    }
    fn cin<T: FromStr>(&mut self) -> T {
        while self.buffer.is_empty() {
            let mut line = String::new();
            let _ = self.stdin.read_line(&mut line);
            for w in line.split_whitespace() {
                self.buffer.push_back(String::from(w));
            }
        }
        self.buffer.pop_front().unwrap().parse::<T>().ok().unwrap()
    }
    fn chars(&mut self) -> Vec<char> {
        self.cin::<String>().chars().collect()
    }
    fn vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.cin()).collect()
    }
}


Measured memory_bytes: 2080
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main() {
  int N, M;
  ll K;
  cin >> N >> M >> K;
  vector<ll> vA(N + 1, 0);
  vector<ll> vB(M + 1, 0);
  for(int i = 0; i < N; i++) {
    ll A;
    cin >> A;
    vA.at(i + 1) = vA.at(i) + A;
  }
  for(int i = 0; i < M; i++) {
    ll B;
    cin >> B;
    vB.at(i + 1) = vB.at(i) + B;
  }
  int ans = 0;
  int k = M;
  for(int i = 0; i < (N + 1); i++) {
    for(int j = k; j >= 0; j--) {
      if((vA.at(i) + vB.at(j)) <= K) {
        if((i + j) > ans) ans = i + j;
        k = j;
        break;
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 6416
#include <bits/stdc++.h>
using namespace std;
int main(){
   string S;
   cin>>S;
   for(int i=0;i<12;i++){
     cout<<S[i];
     if(i==3){
       cout<<" ";
       break;
     }
   }
    for(int i=4;i<12;i++){
      cout<<S[i];
    }
  cout<<endl;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SUM(a) accumulate(all(a), 0LL)
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define FOR(i, m, n) for(int (i)=(m); (i)<(n); i++)
#define FORR(i, m, n) for(int (i)=(n)-1; (i)>=(m); i--)
#define debug(x) cerr << #x << " = " << x << endl
//#define int long long

typedef long long ll;
//ll const MOD = 998244353;
ll const MOD = 1e9+7;
int const inf = 1e9;
ll const INF = 1e18;

inline void ios_(){cin.tie(0); ios::sync_with_stdio(false);}
template<typename T> int size(const T& a){return (int)a.size();}
template<typename T> T Div(T a, T b){return (a + b - 1) / b;}
template<typename T> bool chmin(T& a, const T& b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, const T& b){if(a < b){a = b; return true;} return false;}



signed main(){
    int n, m;
    cin >> n >> m;
    cout << max(0, n*(n-1)/2) + max(0, m*(m-1)/2) << endl;
    return 0;
}


Measured memory_bytes: 256
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, K = read_ints()
    P = [p-1 for p in read_ints()]
    C = read_ints()

    max_score = -math.inf
    for i in range(N):
        cycle_score = C[i]
        scores = [0, C[i]]
        j = P[i]
        k = K
        while k > 1 and i != j:
            cycle_score += C[j]
            scores.append(cycle_score)
            j = P[j]
            k -= 1
        cycle_size = len(scores)-1
        cycle_count = K//cycle_size
        max_score = max(max_score, max(scores[1:]))
        if cycle_count != 0:
            max_score = max(max_score,
                            cycle_score*cycle_count+max(scores[:K%cycle_size+1]),
                            cycle_score*(cycle_count-1)+max(scores[1:]))
    return max_score


if __name__ == '__main__':
    print(solve())


Measured memory_bytes: 84876
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;

int main() {
    int n;
    cin >> n;
    int d[50];
    rep(i, n) {
        cin >> d[i];
    }

    int dd[24] = {};
    dd[0]++;
    rep(i, n) {
        if(dd[d[i]]) {
            dd[(24-d[i])%24]++;
        } else {
            dd[d[i]]++;
        }
    }
    bool x = true;
    vi ii;
    rep(i, 24) {
        if(dd[i] > 1) {
            cout << 0 << endl;
            return 0;
        }
        if(i && dd[i] && !dd[24-i]) {
            if(x) {
                ii.push_back(i);
            }
            x ^= 1;
        }
    }
    for(int xx:ii) {
        swap(dd[xx], dd[24-xx]);
    }
    int ans = INF;
    int now = -5000;
    int s;
    rep(i, 24) {
        if(dd[i]){
            if(now == -5000) {
                s = i;
            }
            ans = min(ans, abs(now-i));
            now = i;
            //cout << i << endl;
        }
    }
    ans = min(ans, abs(s-now+24));
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define mod 1000000007
#define INF2 9999999999
#define INF (1 << 30)
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)

using namespace std;
using ll = __int64_t;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int DX[] = {1, 1, 0, -1, -1, -1, 0, 1};
int DY[] = {0, -1, -1, -1, 0, 1, 1, 1};

void solve(){
    int n, k;
    string s;
    cin >> n >> k >> s;
    char c = tolower(s[k-1]);
    s[k-1] = c;
    cout << s << endl;
}

int main() {
    solve();
    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
	public static void main(String[] args) throws IOException {
		try (BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in))) {

			int r = Integer.parseInt(br.readLine());

			System.out.println(r*r);
		}
	}
}

Measured memory_bytes: 25392
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
ll v[20001], dp[2][1010];
ll a[2][1010],b[2][1010];
int main(){
	ll n,m,k;	cin>>n>>m>>k;
	for(int i=0;i<n;i++){
		cin>>v[i];
	}
	fill((ll*)dp, (ll*)(dp+2), INF);
	fill((ll*)b, (ll*)(b+2), INF);
	/*fill((), ()(), INF);
	for(int i=0;i<2;i++){
		for(int j=0;j<m;j++){
			dp[i][j]=INF;
			b[i][j]=INF;
		}
	}*/
	dp[0][0]=k;	a[0][0]=b[0][0]=v[0];
	for(int i=1;i<n;i++){
		for(int j=0;j<m;j++){
			if(dp[0][j]==INF)	continue;
			//その箱に追加する場合
			if(j+1<m){
				dp[1][j+1]=dp[0][j];
				a[1][j+1]=max((ll)a[0][j],v[i]);
				b[1][j+1]=min((ll)b[0][j],v[i]);
			}
			//新しく箱を作る場合
			ll num=k+dp[0][j];
			num+=(a[0][j]-b[0][j])*(j+1);
			dp[1][0]=min(dp[1][0],num);
			a[1][0]=b[1][0]=v[i];
		}
		for(int j=0;j<m;j++){
			dp[0][j]=dp[1][j];	dp[1][j]=INF;
			a[0][j]=a[1][j];	a[1][j]=0;
			b[0][j]=b[1][j];	b[1][j]=INF;
		}
	}
	ll ans=INF;
	for(int i=0;i<m;i++){
		ll num=dp[0][i];
		num+=(a[0][i]-b[0][i])*(i+1);
		ans=min(ans,num);
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3320
#include<bits/stdc++.h>
using namespace std;

int main(){
  string s;
  cin>>s;
  int zero=0,one=0;
  for(int i=0;i<s.size();i++){
    if(s[i]=='0'){
      zero++;
    }else if(s[i]=='1'){
      one++;
    }
  }
  int ans=min(zero,one);
  cout<<2*ans<<endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <iomanip>
typedef long long ll;
using namespace std;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
#define repi(i, n, init) for (ll i = init; i < (n); i++)

int main()
{
    ll n, r;
    cin >> n >> r;
    if (n > 9)
    {
        cout << r << endl;
    }
    else
    {
        cout << r + 100 * (10 - n) << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using V = vector<ll>;
#define _GLIBCXX_DEBUG
#define rep(i, a, b) for(int i = a; i < b; i++)
#define ALL(v) v.begin(), v.end()

int main(){
    int n; cin>>n;
    string s; cin>>s;

    rep(i,0,s.size()){
        s[i]+=n;
        if(s[i]>'Z'){
            s[i]='A'-1+s[i]-'Z';
        }
    }
    cout<<s<<endl;
}


Measured memory_bytes: 256
while True:
    s = input()
    if s == '-':
        break

    cards = list(s)
    m = int(input())
    for i in range(m):
        h = int(input())
        move = cards[0:h]
        del cards[0:h]
        cards += move

    for i in cards:
        print(i, end='')
    print()




Measured memory_bytes: 5616
#include <iostream>
using namespace std;
int main(void){
    int n;
    cin >> n;
    
    int *h = new int[n];
    for (int i = 0; i < n; i++) {
      cin >> h[i];
    }
    
    int cnt = 0;
    int tmp = 0;
    for (int i = 0; i < n - 1; i++) {
      if (h[i] >= h[i + 1]) {
        tmp++;
      } else {
        tmp = 0;
      }
      if (cnt < tmp) {
        cnt = tmp;
      }
    }
    
    cout << cnt << endl;
    
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

int main()
{
    string s;
    cin >> s;
    int half_size = 0;
    if(s.size() % 2)
    {
        half_size = (s.size() - 1) / 2;
    }
    else
    {
        half_size = s.size() / 2;
    }

    string half = "";
    for(int i = 0; i < half_size; i++)
    {
        half.push_back(s[i]);
    }

    int count = 0;
    for(int i = 0; i < half_size; i++)
    {
        if(half[i] != s[s.size() - 1 - i])
        {
            count++;
        }
    }

    cout << count << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <limits.h>
#include <math.h>

using namespace std;

string s;
vector<int> da(0);

int nibutan(int x, int ri, int le) {
	if (ri - le == 1) {
		return le;
	}
	else {
		int mi = (le + ri) / 2;
		if (da[mi] > x) {
			return nibutan(x, mi,le);
		}
		else {
			return nibutan(x, ri, mi);
		}
	}
}

int main() {
	cin >> s;
	int n = s.size(),co=0;
	for (int i = 0;i < n - 1;i++) {
		if (s[i] == 'R' && s[i + 1] == 'L') {
			da.push_back(i);
			co++;
		}
	}
	vector<int> ans(n);
	for (int i = 0;i < n;i++) {
		if (s[i] == 'L') {
			int po = nibutan(i, co, -1);
			if ((i - da[po]) % 2) {
				ans[da[po] + 1] ++;
			}
			else {
				ans[da[po]] ++;
			}
		}
		else {
			int po = nibutan(i, co, -1);
			if (s[i + 1] == 'L') {
				ans[i]++;
				continue;
			}
			if ((da[po + 1] - i) % 2) {
				ans[da[po + 1] + 1] ++;
			}
			else {
				ans[da[po + 1]] ++;
			}
		}
	}
	for (int i = 0;i < n;i++) {
		if (i == n - 1) {
			cout << ans[i] << endl;
		}
		else {
			cout << ans[i] << ' ';
		}
	}
}

Measured memory_bytes: 1280
// #include {{{
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
// }}}
// #define {{{
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
// }}}

const int P = 1e9 + 7 , D = 60;
inline void pp(int &x,int d) {if((x+=d)>=P)x-=P;}
ll n;
int dig[D] , f[D][2] , pw3[D] , _;

int dfs(int c,int pre) {
  if(c==-1) return 1;
  if(pre>=2) return pw3[c+1];
  if(~f[c][pre]) return f[c][pre];
  int&res=f[c][pre]=0;
  int s=pre*2+dig[c];
  rep(i,0,3) if(i<=s) pp(res,dfs(c-1,s-i));
  return res;
}

int main() {
  cin >> n;
  while(n) dig[_++]=n&1,n>>=1;
  memset(f,-1,sizeof(f));
  rep(i,0,D) pw3[i]=i?pw3[i-1]*3ll%P:1;
  cout << dfs(_-1,0) << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
    int a,b,c,t;
    scanf("%d %d %d",&a,&b,&c);
    if(a>b){
        t=a;
        a=b;
        b=t;
    }
    if(b>c){
        t=b;
        b=c;
        c=t;
    }
    if(a>b){
        t=a;
        a=b;
        b=t;
    }
    printf("%d %d %d\n",a,b,c);
    return 0;
}

Measured memory_bytes: 596
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, M: int, A: "List[str]", B: "List[str]"):
    for i in range(N-M+1):
        for j in range(N-M+1):
            # AとBが等しいか判定
            for k in range(M):
                for l in range(M):
                    if A[i+k][j+l] == B[k][l]:
                        continue
                    else:
                        break
                else:
                    continue
                break    
            else:
                print(YES)
                return

    print(NO)    
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [next(tokens) for _ in range(N)]  # type: "List[str]"
    B = [next(tokens) for _ in range(M)]  # type: "List[str]"
    solve(N, M, A, B)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
fun main(args: Array<String>) {
    while (true) {
        val (H, W) = readLine()!!.split(" ").map(String::toInt)
        if (H == 0 && W == 0) break
        println("#".repeat(W))
        print("#${".".repeat(W-2)}#\n".repeat(H-2))
        println("#".repeat(W))
        println()
    }
}


Measured memory_bytes: 31792
s=input()[::-1]
T=["dream","dreamer","erase","eraser"]
l,n=0,len(s)

while l!=n:
    flag=0
    for i in T:
        word=i[::-1]
        if s[l:l+len(word)]==word:
            l +=len(word)
            flag=1
            break
    if flag==0:print("NO");exit()
print("YES")

Measured memory_bytes: 3188
parseInt(x)=parse(Int, x)
parseMap(x::Array{SubString{String},1})=map(parseInt, x)

function main()
	n = readline() |> parseInt
	s = readline() |> chomp
	r = 0
	k = 0
	for i in 1:n
		if s[i] == 'R'
			r += 1
		end
	end
	for i in 1:n
		if s[i] == 'W'
			if r > 0
				r -= 1
				k += 1
			end
		else
			r -= 1
		end
	end
	println(k)
end

main()

Measured memory_bytes: 158576
n=int(input())
W=[]
ans=0
for i in range(n):
    w=input()
    W.append(w)
    if i>0 and s[len(s)-1]==w[0] and W.count(w)==1:
        ans=1
    elif i>0:
        ans=0
        break
    s=w
if ans==0:
    print("No")
else:
    print("Yes")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define ll long long
#define REV(v) reverse(v.begin(), v.end());
#define REP(i, n) for (ll i = 0; i < n; i++)
#define REPR(i, n) for (ll i = n; i >= 0; i--)
#define FOR(i, start, stop) for (ll i = start; i < stop; i++)
#define FORR(i, start, stop) for (ll i = start; i > stop; i--)
#define SORT(v, n) sort(v, v + n);
#define SORTR(v, n) sort(v, v + n,greater<ll>());
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.begin(), v.end(),greater<ll>());
#define REMOVE(v,n) remove(vector<ll> v,v+v.size(),ll n)
#define ERASE(v,n) v.erase(v.begin()+n);
#define ull unsigned long long
#define pb(a) push_back(a)
#define INF 999999999
#define V(v,i,j) vector(v.begin() + i, v.begin() + j)
#define INSERT(va,vb) va.insert(va.end(), vb.begin(), vb.end())
using namespace std;
typedef vector<ll> vll;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;
int dy[] = {0, 0, 1, -1};
int dx[] = {1, -1, 0, 0};
const int MOD = 1000000007;
void chmin(int &a, int b) { if (a > b) a = b; }

//vector< vector<int> > v (size1, vector<int>(size2) );



int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin>>N;
    vector<ll> A(N);
    FOR(i,0,N)cin>>A[i];
    vector<ll> S(N+1);
    S[0]=0;
    FOR(i,1,N+1)S[i]=S[i-1]+A[i-1];
    VSORT(S);
    //for (auto e:S)cout<<e<<endl;
    ll cnt=1;
    vector<ll> Ans(0);
    FOR(i,0,N){
        if(S[i+1]==S[i]) cnt++;
        else{
            Ans.pb(cnt);
            cnt=1;
        }
    }
    Ans.pb(cnt);
    ll ans=0;
    ll n=0;
    //for (auto e:Ans)cout<<e<<endl;
    FOR(i,0,Ans.size()){
        n=Ans[i];
        ans+=n*(n-1)/2;
    }
    
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 5620
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <climits>
using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define RREP(i,n) for(int i=(int)n-1; i>=0; i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();++i)
#define ALL(c) (c).begin(), (c).end()

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int> > pipii;
typedef vector<int> vi;

const int INF = 1e9;
const int MOD = 1e9+7;

int main(void){
    int n, l;
    while(cin >> n >> l, n || l){
        vector<char> d(n);
        vi p(n);
        REP(i, n) cin >> d[i] >> p[i];
        vector<vi> tunnel(l+2, vi(2, 0));
        REP(i, n){
            if(d[i] == 'R') tunnel[p[i]][0] = i+1;
            else tunnel[p[i]][1] = i+1;
        }
        int cnt = 0;
        while(1){
            cnt++;
            for(int i = l-1; i >= 1; i--){
                if(tunnel[i][0]){
                    tunnel[i+1][0] = tunnel[i][0];
                    tunnel[i][0] = 0;
                }
            }
            for(int i = 1; i <= l-1; i++){
                if(tunnel[i][1]){
                    tunnel[i-1][1] = tunnel[i][1];
                    tunnel[i][1] = 0;
                }
            }
            int f = 0;
            for(int i = 1; i <= l-1; i++){
                if(tunnel[i][0] || tunnel[i][1]) f = 1;
                if(tunnel[i][0] && tunnel[i][1]) swap(tunnel[i][0], tunnel[i][1]);
            }
            if(!f) break;
            tunnel[0][1] = tunnel[l][0] = 0;
        }
        if(tunnel[0][1]) cout << cnt << " " << tunnel[0][1] << endl;
        else cout << cnt << " " << tunnel[l][0] << endl;
    }
    return 0;
}

Measured memory_bytes: 1232
#include <iostream>
#include <string>

#define rep(i,n) for(unsigned int i=0; i<n; i++)

void solve(void){

	int m;					//文字列の行数
	std::string sl;		//文字列格納用ストリング型変数

	char c[10][5] = {
		{},
		{'.',',','!','?',' '},
		{'a','b','c'},
		{'d','e','f'},
		{'g','h','i'},
		{'j','k','l'},
		{'m','n','o'},
		{'p','q','r','s'},
		{'t','u','v'},
		{'w','x','y','z'},
	};

	std::cin >> m;
	while(m--){

		int t = 0;

		std::cin >> sl;

		rep(i,sl.size()-1){
			if(sl[i] == sl[i+1]){
				t++;
			}else{
				if(sl[i]=='7' || sl[i]=='9'){
					t %= 4;
				}
				else if(sl[i]=='1'){
					t %= 5;
				}else{
					t %= 3;
				}
				if(sl[i] != '0'){
					std::cout << c[sl[i]-'0'][t];
				}
				t = 0;
			}
		}
		std::cout << std::endl;
	}
}

int main(void){

	solve();

	return 0;
}

Measured memory_bytes: 0
#include "bits/stdc++.h"
#include <sys/timeb.h>
#include <fstream>

using namespace std;

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define replrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) replrev(i,0,n)
#define repi(itr,ds) for(auto itr = ds.begin(); itr != ds.end(); ++itr)
#define mp make_pair
#define INF 2000000000
#define INFL 2000000000000000000LL
#define EPS 1e-9
#define MOD 1000000007
#define PI 3.1415926536
#define RMAX 4294967295

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<P> vP;
typedef vector<vector<int> > vvi;
typedef vector<vector<bool> > vvb;
typedef vector<vector<ll> > vvll;
typedef vector<vector<char> > vvc;
typedef vector<vector<double> > vvd;
typedef vector<vector<P> > vvP;
typedef priority_queue<int, vector<int>, greater<int> > pqli;
typedef priority_queue<ll, vector<ll>, greater<ll> > pqlll;
typedef priority_queue<P, vector<P>, greater<P> > pqlP;
typedef pair<int, pair<int, int> > Edge;
typedef vector<Edge> vE;
typedef priority_queue<Edge, vector<Edge>, greater<Edge> > pqlE;


//#define DEBUG

#ifdef DEBUG
#define dprintf printf
#define dbg 
#define drepl(i,a,b) repl(i,a,b)
#define drep(i,n) rep(i,n)
#else
#define dprintf (true)?0:printf
#define dbg if(false)
#define drepl(i,a,b) int i; if(false)
#define drep(i,n) int i; if(false)
#endif // DEBUG



int main() {
	string s, t;
	cin >> s >> t;
	vi snum(s.length(), 0), tnum(t.length(), 0);
	rep(i, s.length()) {
		snum[i] = s[i] == 'A' ? 1 : -1;
	}
	rep(i, s.length() - 1) {
		snum[i + 1] += snum[i];
	}
	rep(i, t.length()) {
		tnum[i] = t[i] == 'A' ? 1 : -1;
	}
	rep(i, t.length() - 1) {
		tnum[i + 1] += tnum[i];
	}
	int Q;
	cin >> Q;
	rep(q, Q) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		a--; b--; c--; d--;
		int sd = snum[b] - (a == 0 ? 0 : snum[a - 1]);
		int td = tnum[d] - (c == 0 ? 0 : tnum[c - 1]);
		if (abs(sd - td) % 3 == 0) {
			cout << "YES" << endl;
		}
		else {
			cout << "NO" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1792
using System;
class Program
{
    static void Main(string[] args)
    {
        var line = Console.ReadLine().Split(' ');
        var a = int.Parse(line[0]);
        var b = int.Parse(line[1]);
        var dif = b - a;
        Console.WriteLine(dif * (dif + 1) / 2 - b);
    }
}

Measured memory_bytes: 11092
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
ll N,W,w[100],v[100],A[100001];
int main(){
    cin>>N>>W;
    for(int i=0 ; i<100001 ; i++){
        A[i] = W+1;
    }
    for(int i=0 ; i<N ; i++){
        cin>>w[i]>>v[i];
        for(int j=100000-v[i] ; j>=0 ; j--){
            if(w[i]+A[j]<=W){
                A[j+v[i]] = min(A[j+v[i]],A[j]+w[i]);
            }
        }
        A[v[i]] = min(A[v[i]],w[i]);
    }
    ll ans = 0;
    for(int i=0 ; i<=100000 ; i++){
        if(A[i]<=W)ans = i;
    }
    cout<<ans;
}

Measured memory_bytes: 1024
<?php
fscanf(STDIN, "%d%d%d", $k, $a, $b);
if($b - $a < 2){
  echo 1+$k;
}else{
  if($k < $a){
    echo 1+$k;
  }else{
    if(($k - $a - 1)%2 == 0){
      $ans = $a + ($k - $a + 1)/2*($b-$a);
    }else{
      $ans = $a + 1 + ($k - $a)/2*($b-$a);
    }
    printf("%d", $ans);
  }
}

Measured memory_bytes: 4728
#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(ll i=0;i<(n);i++)
#define REAP(i,a,n) for(ll i=(a);i<(n);i++)
#define YES cout<<"Yes"<<endl
#define NO cout<<"No"<<endl
#define fr first
#define sc second
#define pb push_back
#define All(v) v.begin(),v.end()

typedef long long ll;


int main(){
    ios::sync_with_stdio(false);
    ll n,m;
    cin >> n >> m;
    vector<pair<ll,ll> > ps(m);
    vector<ll> a(n);
    REP(i,n) cin >> a[i];
    REP(i,m){
        ll b,c;
        cin >> b >> c;
        ps[i] = make_pair(c,b);
    }
    sort(All(a), greater<ll>() );
    sort(All(ps), greater<pair<ll,ll> >() );

    ll sum=0;
    ll ai=0,pi=0;
    for(ll i=0;i<n;){
        if (ps[pi].fr > a[ai]){
            if(n-i < ps[pi].sc){
                sum+=ps[pi].fr*(n-i);
                break;
            }else{
                sum+=ps[pi].fr*ps[pi].sc;
                i+=ps[pi].sc;
            }
            pi++;
        }else{
            sum+=a[ai];
            i++;
            ai++;
        }
    }
    cout << sum << endl;



}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
int arr[100005];

int find(int x)
{ // find the father point

	return arr[x] < 0 ? x : (arr[x] = find(arr[x])); // update every child to the other father
}

void Union(int x, int y){
	x = find(x);
	y = find(y);
	if(x == y)
		return;

	if(arr[x] <= arr[y])
	{
		arr[x] += arr[y];
		arr[y] = x;
	}

	else{
		arr[y] += arr[x];
		arr[x] = y;
	}

}

int main(int argc, char const *argv[])
{
	int n,m,x,y,z;
	while(~scanf("%d %d",&n,&m)){
		
		bool check[n+5];
		for (int i = 0; i < n+5; ++i)
		{
			arr[i]=-1;
			check[i]=false;
		}
		for (int i = 0; i < m; ++i)
		{
			scanf("%d %d %d",&x,&y,&z);
			Union(x,y);
			
		}
		int ans=0;
		for (int i = 1; i < n+1; ++i)
		{
			if (arr[i]<0)
			{
				ans++;
			}
		}
		printf("%d\n",ans );
	}

	return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REP2(i, n) for (int i = 1; i <= (int)(n); i++)
#define FOR(i, m, n) for (int i = m; i n; i++)
#define SORT(x) sort(x.begin(), x.end())
#define REVE(x) reverse(x.begin(), x.end())
#define all(x) (x).begin(), (x).end()
struct initon
{
    initon()
    {
        cin.tie(0);
        ios::sync_with_stdio(false);
    };
};
int k=0,n=0, m=0, l=0,a=0, b=0, c=0, d=0,ans=0,ans2=0;
string s;
signed main() {
    cin >> n ;
    vector<int> A(n);
  REP(i,n)cin>>A[i];
    SORT(A);  
  REP(i,n){
    if(i%2==0){
        ans += A[i];
    }
        else {
          ans-=A[i];
        }
    
    }
    cout << abs(ans);
}

Measured memory_bytes: 3576
// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input = input.split("\n");
	input = input[0];

	var ans = "";
	for(var i = 1; i <= input.length; i = i + 2){
		ans += input[i-1];
	}
	console.log(ans);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 10188
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 55;
const int INF = 1e15 + 123;

void minimize(int &x, int y) {
	x = (x > y) ? y : x;
}

int n, X, D;
vector <int> g[N];
int s[N], c[N];
int dp[N][N * N * N];
int lim1[N], lim2[N];

// precalculate
void dfs(int u) {
	c[u] = 1;
 	for (int &v : g[u]) {
		dfs(v);
		c[u] += c[v];
		s[u] += s[v];
	}
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> X >> D;
	cin >> s[1];
	for (int i = 2; i <= n; ++i) {
		int p; cin >> s[i] >> p;
		g[p].push_back(i);	
	}

	dfs(1);
	
	// dp
	for (int i = 1; i <= n; ++i) {
		int lim = INF;
		if (i > 1) lim = D;
		lim1[i] = min(lim, 50LL);
		lim2[i] = lim - lim1[i];
	}

	// cost s[i], gain c[i]

	// bag1: knapsack (total gain <= N^3)
	// dp[i][total] = min weight
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j < N * N * N; ++j) {
			dp[i][j] = INF;
		}
	}
	dp[0][0] = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < N * N * N; ++j) {
			int mx = min(lim1[i], j / c[i]);
			for (int take = 0; take <= mx; ++take) {
				minimize(dp[i][j], dp[i - 1][j - take * c[i]] + take * s[i]);
			} 
		}
	}

	// greedily choose items in bag 2
	vector <int> p;
	for (int i = 1; i <= n; ++i) p.push_back(i);
	sort(p.begin(), p.end(), [&](int x, int y){
		return 1LL * c[x] * s[y] > 1LL * c[y] * s[x];
		// c[x] / s[x] > c[y] / s[y]
	});


	int res = 0;
	for (int j = 0; j < N * N * N; ++j) {
		int rem = X - dp[n][j];
		int tot = j;
		if (rem < 0) continue;
		for (int &i : p) {
			int take = min(lim2[i], rem / s[i]);
			tot += c[i] * take;
			rem -= s[i] * take;
		}
		res = max(res, tot);
	}

	cout << res << '\n';
}


Measured memory_bytes: 67968
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,k;
    
    cin >> n >> k;
  	int nos[n];
  	for(int i=0;i<n;i++){
      nos[i]=0;
    }
    for(int i=0;i<k;i++){
    	int d;
        cin >> d;
        for(int j=0;j<d;j++){
        	int a;
       		cin >> a;
            nos[a-1]++;
        }
    }
    int ans = 0;
    for(int i=0;i<n;i++){
    	if(nos[i]==0)ans++;
    }
    cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3552
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

#define int ll

//defines
typedef long long ll;
typedef double ld;
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define prev _prev
#define y0 _y0
#define kill _kill

//permanent constants
const ld pi = acos(-1.0);
const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int digarr[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
const int alf = 26;
const int dig = 10;
const int two = 2;
const int th = 3;
const ll prost = 239;
const ll btc = 30;
const ld eps = 1e-8;
const ll INF = (ll)(1e18 + 239);
const int BIG = (int)(2e9 + 239);
const ll MOD = 998244353;

//random
#ifdef ONPC
mt19937_64 rnd(239);
#else
mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

//constants
const int M = (int)(2e5 + 239);
const int N = (int)(2e3 + 239);
const int L = 25;
const int T = (1 << 18) + 239;
const int B = 500;
const int X = 3010;

int power(int a, int k)
{
    if (k == 0)
        return 1;
    int t = power(a, k >> 1);
    t = 1LL * t * t % MOD;
    if (k & 1)
        t = 1LL * t * a % MOD;
    return t;
}

int a, b, c, d;
int dp[X][X];
int p[X][X], inv[X][X];
int pref[X][X];

int32_t main()
{
#ifdef ONPC
    freopen("input", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    for (int i = 1; i < X; i++)
    {
        p[i][0] = 1;
        for (int j = 1; j < X; j++)
            p[i][j] = 1LL * p[i][j - 1] * i % MOD;
        int iv = power(i, MOD - 2);
        inv[i][0] = 1;
        for (int j = 1; j < X; j++)
            inv[i][j] = 1LL * inv[i][j - 1] * iv % MOD;
    }
    cin >> a >> b >> c >> d;
    c -= a;
    d -= b;
    dp[0][0] = 1;
    for (int i = 1; i <= d; i++)
    {
        pref[i - 1][0] = 0;
        for (int j = 1; j <= c; j++)
        {
            pref[i - 1][j] = pref[i - 1][j - 1];
            pref[i - 1][j] += 1LL * dp[i - 1][j - 1] * inv[b + i - 1][j - 1] % MOD;
            if (pref[i - 1][j] >= MOD)
                pref[i - 1][j] -= MOD;
        }
        for (int j = 0; j <= c; j++)
        {
            dp[i][j] = 1LL * dp[i - 1][j] * (j + a) % MOD;
            dp[i][j] += 1LL * pref[i - 1][j] * p[b + i - 1][j] % MOD;
            if (dp[i][j] >= MOD)
                dp[i][j] -= MOD;
        }
    }
    int ans = 0;
    int pw = 1;
    for (int i = c; i >= 0; i--)
    {
        ans += 1LL * dp[d][i] * pw % MOD;
        if (ans >= MOD)
            ans -= MOD;
        pw = 1LL * pw * (b + d) % MOD;
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 286232
#include<iostream>
 using namespace std; 
bool isP(int x){ if(x==0||x==1)return false;
 for(int i=2;i*i<=x;i++)
{ 
if(x%i==0)return false; 
} 
return true;
 }
 int main()
{ 
int n,a,cnt=0;
 cin>>n;
 for(int i=0;i<n;i++)
{ 
cin>>a; cnt+=isP(a);
 } 
cout<<cnt<<endl;
 } 



 



Measured memory_bytes: 3100
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    print((n-1)>>1)
    return

#Solve
if __name__ == "__main__":
    solve()


Measured memory_bytes: 39408
import sys

input = sys.stdin.readline

def main():
    N, C = map(int, input().split())
    
    event = []
    
    for i in range(N):
        s, t, c = map(int, input().split())
        event.extend([[s, c-1, 1], [t+0.5, c-1, 0]])
        
    event.sort()
    
    nums = [0] * C
    ans = cur = 0
    
    for e, c, m in event:
        if m:
            if not nums[c]: 
                cur += 1
                ans = max(ans, cur)
            nums[c] += 1
        else:
            nums[c] -= 1
            if not nums[c]: cur -= 1
            
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 31112
#include <iostream>
#include <map>
using namespace std;

int main() {
    int n; cin >> n;
    map<int, int> nums;
    for (int i = 0; i < n; i++) {
        int a; cin >> a;
        nums[a]++;
    }

    int ans = 0;
    for (auto ite : nums) {
        int num = ite.second;
        if (num % 2 == 1) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 4864
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b;
  cin >> a >> b;

  if (a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0){
    cout << "Possible" << endl;
  }
  else {
    cout << "Impossible" << endl;
  }
}

Measured memory_bytes: 256
main :: IO ()
main = do
    [n,m,x] <- map read . words <$> getLine :: IO [Int]
    as <- map read . words <$> getLine :: IO [Int]
    putStrLn $ show $ if (length (filter (<x) as) <= length (filter (>x) as)) then length (filter (<x) as) else length (filter (>x) as)

Measured memory_bytes: 892
a, b, c, d = map(int, input().split())
def gcd(a, b):
    return b if a == 0 else gcd(b % a, a)
def lcm(a, b):
    return a // gcd(a, b) * b
def count(x):
    return x - (x // c) - (x // d) + (x // lcm(c, d))
print(count(b) - count(a - 1))

Measured memory_bytes: 3060
#include <bits/stdc++.h> 

using namespace std;

int main()
{
	int n , k, x, ans=0;
	cin >> n >> k;
	multiset < int > v;
	while(n--){
		cin >> x;
		v.insert(x);
	}
	x=0;
	for(auto MMB : v){
		if(x == k) break;
		ans += MMB;
		x++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3604