akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <iomanip>


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<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define rep(i, a, b) for (int i=a; i<(b); i++)
#define rp(i, a) for (int i=0; i<(a); i++)
#define repd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define rpd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define shandom_ruffle random_shuffle

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout << std::setprecision(9);
    cout << std::fixed;

    ll n,k;
    cin >> n >> k;
    cout << (n-1)*(k-1)<<endl;

    return 0;
}

// read the question correctly (ll vs int)
// template by super1 derived from bqi343


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

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pii pair <int, int>
#define pll pair <ll, ll>
#define gcd __gcd
#define all(a) a.begin(), a.end()
#define sz(a) (ll)(a.size())
#define endl "\n"

const ll L = 1e5+5;

vector <ll> adj[2*L];
bool visited[2*L];

ll X = 0, Y = 0;

void dfs(ll s)
{
    visited[s] = true;

    if(s<L)
    {
        X++;
    }

    else
    {
        Y++;
    }

    for(auto i: adj[s])
    {
        if(!visited[i])
        {
            dfs(i);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    ll N;
    cin >> N;

    for(ll i=0; i<N; i++)
    {
        ll x, y;
        cin >> x >> y;

        y+=L;

        adj[x].pb(y);
        adj[y].pb(x);
    }

    ll ans = 0;

    for(ll i=0; i<2*L; i++)
    {
        if(!visited[i])
        {
            X = 0, Y = 0;
            dfs(i);
            ans+=(X*Y);
        }
    }

    cout << ans-N << endl;

    return 0;
}

Measured memory_bytes: 10240
def main():
    from collections import Counter
    n = int(input())
    V = map(int,input().split())
    odds = []
    evens = []
    for i,v in enumerate(V):
        if i & 1:
            evens.append(v)
        else:
            odds.append(v)
    
    odds_modes= Counter(odds).most_common(2)
    evens_modes = Counter(evens).most_common(2)

    if odds_modes[0][0] != evens_modes[0][0]:
        print(len(odds)- odds_modes[0][1] + len(evens) - evens_modes[0][1])
    else:
        odds_modes.append((-1,0))
        evens_modes.append((-1,0))

        print(
            min(
                len(odds)-odds_modes[0][1] + len(evens) - evens_modes[1][1],
                len(odds)-odds_modes[1][1] + len(evens) - evens_modes[0][1],
            )
        )
            

main()

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

int main() {
  char c;
  cin >> c;
  if (c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o' )
    cout << "vowel" << endl;
  else
    cout << "consonant" << endl;
}
  


Measured memory_bytes: 256
base = 127
mask = (1 << 32) - 1


def calc_hash(f, pl, tl):
    dl = tl - pl
    tmp = set()

    t = 1
    for _ in range(pl):
        t = (t * base) & mask
    e = 0
    for i in range(pl):
        e = (e * base + f[i]) & mask
    for i in range(dl):
        tmp.add(e)
        e = (e * base - t * f[i] + f[i + pl]) & mask
    tmp.add(e)
    return tmp


t = [ord(c) for c in input().strip()]
tl = len(t)
q = int(input())
ps = [input().strip() for _ in range(q)]
h = dict()
a = []
hash_len = 19
for p in ps:
    p = [ord(c) for c in p]
    pl = len(p)
    if pl > tl:
        a.append(0)
        continue
    bs = min(hash_len, pl)
    keys = calc_hash(p, bs, pl)
    if bs not in h:
        h[bs] = calc_hash(t, bs, tl)
    a.append(1 if keys.issubset(h[bs]) else 0)
print('\n'.join(map(str, a)))

Measured memory_bytes: 1081044
// 基本テンプレート

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
using namespace std;

#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long int

template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}

typedef pair<int, int> pii;
typedef long long ll;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
constexpr ll INF = 1001001001001001LL;
constexpr ll MOD = 1000000007LL;

const int MAXN = 1010;
const int MAXX = 5010;
vector<int> G[MAXN];
int N, x[MAXN], dp[MAXN], dp2[MAXN][MAXX];
bool ok = true;

int solve_dp(vector<int> &a, vector<int> &b, int &lim) {
    int M = a.size();
    repq(i,0,M) repq(j,0,lim) dp2[i][j] = INF;
    dp2[0][0] = 0;
    rep(i,0,M) repq(j,0,lim) {
        if(dp2[i][j] == INF) continue;

        // choose a
        if(j + a[i] <= lim) {
            chmin(dp2[i+1][j+a[i]], dp2[i][j] + b[i]);
        }

        // choose b
        if(j + b[i] <= lim) {
            chmin(dp2[i+1][j+b[i]], dp2[i][j] + a[i]);
        }
    }
    return *min_element(dp2[M], dp2[M]+lim+1);
}

void solve(int p, int par=-1) {
    bool leaf = true;
    vector<int> a, b;
    for(auto to : G[p]) {
        if(to == par) continue;
        leaf = false;
        solve(to, p);
        a.push_back(x[to]);
        b.push_back(dp[to]);
    }
    if(leaf) dp[p] = 0;
    else {
        int val = solve_dp(a, b, x[p]);
        if(val == INF) {
            cout << "IMPOSSIBLE" << endl;
            exit(0);
        }
        dp[p] = val;
    }
}

signed main() {
    cin >> N;
    rep(i,0,N-1) {
        int p; cin >> p; p--;
        G[p].push_back(i+1);
    }
    rep(i,0,N) {
        cin >> x[i];
        dp[i] = INF;
    }
    
    solve(0);
    cout << (!ok ? "IMPOSSIBLE" : "POSSIBLE") << endl;
    return 0;
}

Measured memory_bytes: 37376
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();

		int one = 0;
		int zero = 0;

		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == '0') {
				one++;
			} else {
				zero++;
			}
		}

		System.out.println(Math.min(one, zero) * 2);
	}
}


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

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(o, 1, (n))
#define pb push_back
#define INF 1000000000000000000
#define PI 3.14159265358979323846
#define f first
#define s second
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
typedef vector<int> vi;
typedef vector<pii> vii;

int main()
{
    FAST_IO;

    priority_queue<pii, vii, greater<pii> > q;
    int n;
    cin >> n;
    REP(n) {
        int a, b;
        cin >> a >> b;
        q.push({b, a});
        if (b < a) {
            cout << "No" << endl;
            return 0;
        }
    }

    ll currT = 0;
    bool ok = true;
    while (!q.empty() && ok) {
        int b = q.top().f, a = q.top().s;
        //cout << "  " << a << " " << b << "   " << currT << endl;
        q.pop();
        if (b < currT+a) {
            ok = false;
            break;
        }
        currT += a;
    }

    if (ok) cout << "Yes";
    else cout << "No";
    cout << endl;

    return 0;
}


Measured memory_bytes: 2420
n = int(input())
lis = list(map(int,input().split()))
li = [0]
for i in range(n):li.append(li[-1]+lis[i])
ans = 0
num = 0
li.sort()
for i in range(n):
  if li[i] == li[i+1]:
    num += 1
    ans += num
  else:num = 0
print(ans)

Measured memory_bytes: 26720
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
 
using namespace std;
 
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P > PP;

class Ant{
public:
  char dir;
  int pos;
  Ant(char _d,int _p) : dir(_d), pos(_p) {}
  Ant() : dir('\0'), pos(-1) {}
};

int main(){
  int total_ants;
  int tunnel_length;
  while(scanf("%d %d",&total_ants,&tunnel_length)){
    if(total_ants == 0) break;

    Ant ants[101];
    for(int ant_idx=0; ant_idx < total_ants; ant_idx++){
      char dir[2];
      int pos;
      scanf("%s %d",dir,&pos);
      ants[ant_idx] = Ant(dir[0],pos);
    }

    int last_time = 0;
    int last_ant = 0;
    for(int time=1;time <= tunnel_length * total_ants;time++){
      int collapse[101];
      memset(collapse,0,sizeof(collapse));
      int rem = 0;
      for(int ant_idx=0; ant_idx < total_ants; ant_idx++){
        if(ants[ant_idx].pos == 0
           || ants[ant_idx].pos == tunnel_length) continue;

        rem |= (1 << ant_idx);
        if(ants[ant_idx].dir == 'R'){
          collapse[ants[ant_idx].pos + 1] |= (1 << ant_idx);
        }

        else if(ants[ant_idx].dir == 'L'){
          collapse[ants[ant_idx].pos - 1] |= (1 << ant_idx);
        }
      }

      if(rem == 0) break;

      for(int i=1;i<tunnel_length;i++){
        if(__builtin_popcount(collapse[i]) >= 2){
          for(int ant_idx=0; ant_idx < total_ants; ant_idx++){
            if(collapse[i] & (1 << ant_idx)){
              ants[ant_idx].pos += (ants[ant_idx].dir == 'R' ? 1 : -1);
              ants[ant_idx].dir = (ants[ant_idx].dir == 'R' ? 'L' : 'R');
              rem &= ~(1 << ant_idx);
            }
          }          
        }
      }

      int tmp_ant = -1;
      for(int ant_idx=0; ant_idx < total_ants; ant_idx++){
        if(rem & (1<< ant_idx)){
          if(ants[ant_idx].dir == 'R'){
            ants[ant_idx].pos++;
            if(ants[ant_idx].pos == tunnel_length){
              if(tmp_ant == -1){
                tmp_ant = ant_idx;
              }
            }
          }
          else if(ants[ant_idx].dir == 'L'){
            ants[ant_idx].pos--;
            if(ants[ant_idx].pos == 0){
              tmp_ant = ant_idx;
            }
          }
        }
      }

      last_ant = tmp_ant;
      last_time = max(last_time,time);
    }
    
    printf("%d %d\n",last_time,last_ant + 1);
  }
}

Measured memory_bytes: 1196
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    string s;
    cin >> s;
    for(int i= 0; i< 3; i++){
        if(s[i] == '7'){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3128
#include <cstdio>
#include <cstdint>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <utility>

int main() {
  intmax_t N;
  size_t M;
  intmax_t p;
  scanf("%jd %zu %jd", &N, &M, &p);

  std::vector<intmax_t> d(M);
  for (auto& di: d) {
    scanf("%jd", &di);
    di -= p;
    if (di < 0) di += N;
  }
  p = 0;
  std::sort(d.begin(), d.end());

  intmax_t res = std::min(d[M-1], N-d[0]);
  for (size_t i = 0; i+1 < M; ++i) {
    intmax_t r = d[i];
    intmax_t l = d[i+1];
    intmax_t d0 = r;
    intmax_t d1 = N-l;
    intmax_t cur = d0 + d1 + std::min(d0, d1);
    res = std::min(res, cur);
  }
  printf("%jd\n", 100*res);
}



Measured memory_bytes: 2812
x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
l=[]
L=[]
for ix in range(x):
  for iy in range(y):
    l.append(a[ix]+b[iy])
l.sort()
l.reverse()
if len(l)>k:
  l=l[0:k]
for iz in range(z):
  for i in range(len(l)):
    L.append(c[iz]+l[i])
L.sort()
L.reverse()
for i in range(k):
  print(L[i])

Measured memory_bytes: 135304
#include <iostream>
using namespace std;
typedef long long ll;
ll a,b;

int main(){
	cin >> a >> b;
	if(a<=0 && b>=0) cout << "Zero" << endl;
	else if(a<0 && (a-b)%2==0) cout << "Negative" << endl;
	else cout << "Positive" << endl;
}

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

#ifdef LOCAL
#include "../../dump.hpp"
#else
#define dump(...)
#endif

#define int ll
#define rep(i,n) for(int i=0,i##_cond=(n);i<i##_cond;++i)
#define FOR(i,a,b) for(int i=(a),i##_cond=(b);i<i##_cond;++i)
#define ROF(i,a,b) for(int i=(a)-1,i##_cond=(b);i>=i##_cond;--i) // ROF(i,n,0)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend() //sortで降順
#define SUM(a) accumulate(all(a),int(0))
using ll  = long long;
using vi  = vector<int>;
using vvi = vector<vi>;
using vs  = vector<string>;
using pii = pair<int,int>;
constexpr ll inf = 1ll<<61;
constexpr ll mod = 1e9+7;
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T>T add(const T &a, const T &b){return (a+b)%mod;}

template< unsigned mod >
struct RollingHash {
  vector< unsigned > hashed, power;

  inline unsigned mul(unsigned a, unsigned b) const {
    unsigned long long x = (unsigned long long) a * b;
    unsigned xh = (unsigned) (x >> 32), xl = (unsigned) x, d, m;
    asm("divl %4; \n\t" : "=a" (d), "=d" (m) : "d" (xh), "a" (xl), "r" (mod));
    return m;
  }

  RollingHash(const string &s, unsigned base = 10007) {
    int sz = (int) s.size();
    hashed.assign(sz + 1, 0);
    power.assign(sz + 1, 0);
    power[0] = 1;
    for(int i = 0; i < sz; i++) {
      power[i + 1] = mul(power[i], base);
      hashed[i + 1] = mul(hashed[i], base) + s[i];
      if(hashed[i + 1] >= mod) hashed[i + 1] -= mod;
    }
  }

  unsigned get(int l, int r) const {
    unsigned ret = hashed[r] + mod - mul(hashed[l], power[r - l]);
    if(ret >= mod) ret -= mod;
    return ret;
  }

  unsigned connect(unsigned h1, int h2, int h2len) const {
    unsigned ret = mul(h1, power[h2len]) + h2;
    if(ret >= mod) ret -= mod;
    return ret;
  }

  int LCP(const RollingHash< mod > &b, int l1, int r1, int l2, int r2) {
    int len = min(r1 - l1, r2 - l2);
    int low = -1, high = len + 1;
    while(high - low > 1) {
      int mid = (low + high) / 2;
      if(get(l1, l1 + mid) == b.get(l2, l2 + mid)) low = mid;
      else high = mid;
    }
    return (low);
  }
};

using RH = RollingHash< 1000000007 >;

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

  RH rh(s);
  int ans = 0;
  rep(i,n) FOR(j,i+1,n){ // i : 左, j : 右
    int ok = 0;
    int ng = n;
    while(abs(ok - ng) > 1){
      int mid = (ok + ng) / 2; // 文字数
 
      bool f;
      if(i+mid <= j and j+mid <= n){
	if(rh.get(i,i+mid) == rh.get(j,j+mid))
	  f = true;
	else f = false;
      }else{
	f = false;
      }
      
      if(f){
	ok = mid;
      }else{
	ng = mid;
      }
    }
    chmax(ans,ok);
  }
  cout << ans << endl;
}  


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
////#define _USE_MATH_DEFINES
#include<stdio.h>
#include<stdlib.h>
//#include<math.h>
//#include<string.h>
//#include<time.h>
#define P(type,x) fprintf(stdout,"%"#type"\n",x)
typedef struct LIST{
	struct LIST *next;
	struct LIST *prev;
	int value;
}NODE,*PNODE;

PNODE list;
void Add(int);
void Del(int);
void DelFirst();
void DelLast();
void DelNode(PNODE);
void Display();
void Release();

int main() {
	list = (NODE*)malloc(sizeof(NODE));
	list->next = list;
	list->prev = list;
	int fig,n,f;
	char op[13];
	fscanf(stdin, "%d", &n),getchar();
	while (n--) {
		fscanf(stdin, "%[^\n]*s", op),getchar();
		f = 0;
		if (*op == 'i') { f = 1; }
		else if (*op == 'd') {
			switch (*(op+6)) {
			case 'F':
				DelFirst();
				break;
			case 'L':
				DelLast();
				break;
			default:
				f = 2;
				break;
			}
		}
		if (f) {
			fig = atoi(&op[7]);
			if (f == 1) Add(fig);
			else if (f == 2) Del(fig);
		}
	}
	Display();
	Release();
	return 0;
}

void Add(int tmp){
	PNODE p = (NODE*)malloc(sizeof(NODE));
	p->value = tmp;
	p->next = list->next;
	p->prev = list;
	list->next->prev = p;
	list->next = p;
}

void Del(int tmp){
	PNODE cur = list->next;
	while (cur != list) {
		if (cur->value == tmp) {
			DelNode(cur);
			return;
		}
		cur = cur->next;
	}
}

void DelFirst(){
	DelNode(list->next);
}

void DelLast(){
	DelNode(list->prev);
}

void DelNode(PNODE node){
	if (node == list) return;
	node->next->prev = node->prev;
	node->prev->next = node->next;
}

void Display() {
	if (list->next == list) { puts("list is empty"); return; }
	NODE *p= list->next;
	fprintf(stdout, "%d", p->value);
	p = p->next;
	for (; p != list; p = p->next) fprintf(stdout, " %d", p->value);
	puts("");
}

void Release(){
	NODE *next, *del;
	next = list->next;
	while (next != list){
		del = next;
		next = next->next;
		free(del);
	}
}

Measured memory_bytes: 34988
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;
typedef unsigned long ul;
typedef pair<ul, ul> P;

int main(){
    int r, D, x2k;
    int year[11];

    cin >> r >> D >> x2k;
    year[0] = x2k;
    rep(i, 10){
        year[i + 1] = r * year[i] - D;
        cout << year[i + 1] << endl;
    }
} 

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vvi vector<vector<int>> 
#define vi vector<int> 
#define vpii vector<pair<int,int>> 
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define ffor(i,n) for(int i = 0; i < n; ++i)
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    if(n&1)
    {
        cout << "No";
        return 0;
    }
    string s;
    cin >> s;

    int hf = (n/2) - 1;
    for(int i = 0; i <= hf; ++i)
    {
        if(s[i] != s[i + n/2])
        {
            cout << "No";
            return 0;
        }
    }

    cout << "Yes";
}

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

using namespace std;
 
typedef long long ll;
 

ll gcd(int x, int y){ return y?gcd(y, x%y):x;}

int main(){
    int n;

    cin >> n;
    vector<int> a;
    for(int i = 0; i < n; i++)
    {
        int tmp;
        cin >> tmp;
        a.push_back(tmp);
    }

    ll ans = gcd(a[0],a[1]);
    for(int i = 2; i < n ; i++)
    {
        ans = gcd(ans, a[i]);

    }
        
    cout << ans << endl;

}

Measured memory_bytes: 1020
#include <iostream>
using namespace std;
 
long long fn(long long n, long long x){
  if(n < 0) return 0;
  else return (n/x + 1);
}
 
int main(){
  long long a, b, x, count;
  
  cin >> a >> b >> x;
  cout << fn(b, x) - fn(a-1, x) << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<algorithm>
#include<string>

using namespace std;

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

        int three=n/100,two=(n-three*100)/10,one=(n%100)-(two*10);

        if((three<two)||((three==two)&&(two<one))) cout<<three+1<<three+1<<three+1;
        else cout<<three<<three<<three;

        cout<<endl;

        return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false); 
    int N;
    cin >> N;
    ll a[3 * N];

    for(int i = 0; i < 3 * N; ++i) cin >> a[i];
    sort(a, a + 3 * N, greater<int>());

    ll res = 0;
    for(int i = 1; i < 2 * N; i += 2) res += a[i];

    cout << res << endl;
}

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

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int w[110];
int v[110];

// DP テーブル
long long dp[110][100010];

int main() {
    int N; cin >> N;
    int W; cin >> W;
    rep(i,N){
      cin>>w[i];
      cin>>v[i];
    }

    rep(i,110)rep(j,100010){
      dp[i][j]=0;
    }

    // ループ
    for(int i=0; i<N; i++){
      for(int sum_w=1; sum_w<=W; sum_w++){
        if(sum_w-w[i]>=0){
          chmax(dp[i+1][sum_w],dp[i][sum_w-w[i]]+v[i]);
        }
        chmax(dp[i+1][sum_w],dp[i][sum_w]);
      }
    }
    // 答え
    cout<<dp[N][W]<<endl;
}

Measured memory_bytes: 86144
#include<bits/stdc++.h>
using namespace std;
const int mx = 1000010;
long long a[mx][3]; 
bool possible[mx];
main()
{
	int n;
	cin >> n;
	for(int i=0; i<n; i++)
	cin >> a[i][0] >> a[i][1] >> a[i][2];
	
	for(int i = 1; i < n; i++){
		a[i][0] += max(a[i-1][1], a[i-1][2]);
		a[i][1] += max(a[i-1][0], a[i-1][2]);
		a[i][2] += max(a[i-1][0], a[i-1][1]);
		
	}
	cout << max(max(a[n-1][0], a[n-1][1]), a[n-1][2]);
	
return 0;
}


Measured memory_bytes: 3328
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstdio>
#include <numeric>
#include <cmath>

#define rep(i, n) for(int i = 0;i < (int)(n); i++)
#define pb push_back
typedef long long ll;

using namespace std;


ll gcd(ll x, ll y)
//最大公約数
{
    ll r;

    if(x == 0 || y == 0)
    {
        fprintf(stderr, "引数エラーです。\n");
        return 0;
    }

    while((r = x % y) != 0)
    {
        x = y;
        y = r;
    }
    return y;
}

ll lcm(ll m, ll n )
//最小公倍数
{
    // 引数に０がある場合は０を返す
    if ( ( 0 == m ) || ( 0 == n ) )
        return 0;

    return ((m / gcd(m, n)) * n);
}

int main() {
    int n;
    cin >> n;
    ll ans = 1;
    vector<ll> t(n);
    rep(i, n) cin >> t[i];
    rep(i,n) ans = lcm(ans,t[i]);
    cout << ans << endl;
    return 0;
}


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

int main(){
    int N,count=0;
    cin>>N;
    int A[N];

    for(int i=0;i<N;i++){
        cin>>A[i];
    }

    for(int i=0;i<N;i++){
        int minj=i;
        for(int j=i;j<N;j++){
            if(A[j]<A[minj]){
                minj=j;
            }
        }
        if(minj!=i){
            int k=A[minj];
            A[minj]=A[i];
            A[i]=k;
            count+=1;
        }
        
    }

    for(int i=0;i<N;i++){
        if(i!=N-1){
            cout<<A[i]<<" ";
        }else{
            cout<<A[i]<<endl;
        }
    }
    cout<<count<<endl;
}


Measured memory_bytes: 3096
from collections import deque

n, x, y = map(int, input().split())

graph = [[i-1,i+1] for i in range(n+1)]
graph[1]=[2]
graph[n]=[n-1]
graph[0]=[0]

graph[x].append(y)
graph[y].append(x)

def bfs(start,graph2):
    dist = [-1] * (n+1)
    dist[0] = 0
    dist[start] = 0

    d = deque()
    d.append(start)
    while d:
        v = d.popleft()
        for i in graph2[v]:
            if dist[i] != -1:
                continue
            dist[i] = dist[v] + 1
            d.append(i)
        
    dist = dist[start+1:]
    return dist

ans=[0 for _ in range(n-1)]
for i in range(1,n+1):
    for j in bfs(i,graph):
        ans[j-1] +=1
 
for i in ans:
    print(i)

Measured memory_bytes: 75788
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
int gcd(int a, int b) {
	if (b == 0) {
		return a;
	}
	return gcd(b, a % b);
}

int main()
{
	long long int i, j, k, l, m,N,X,H,M,W, n,A,B, sum, flag, cc, cnt;
	sum = 0;
	flag = 1;
	cin >> H >> W;
	char a[10001];
	int len[50] = {};
	for (i = 0; i <= H*W-1; i++) {
			cin >> a[i];
	}
	sort(a, a + H * W);
	cc = a[0];
	for (i = 0; i <= H * W - 1; i++) {
		if (a[i] == cc) {
			len[sum]++;
		}
		else {
			cc = a[i];
			sum++;
			len[sum]++;
		}

	}
	
	int fla = 1;
	cc = 0;
	cnt = 0;
	int cnt1 = 0;
	if (H % 2 == 0 && W % 2 == 0) {
		for (i = 0; i <= sum; i++) {
			if (len[i] % 4 != 0) {
				fla = 0;
				break;
			}
		}
		if (fla == 1)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
	else if (H % 2 == 1 && W % 2 == 0) {
		for (i = 0; i <= sum; i++) {
			if (len[i] % 2 == 1) {
				fla = 0;
				break;
			}
			else if (len[i] % 4 == 2) {
				cc++;
			}
		}
		if (fla != 0 && cc <= W / 2) {
			cout << "Yes" << endl;
		}
		else
			cout << "No" << endl;

	}
	else if (H % 2 == 0 && W % 2 == 1) {
		for (i = 0; i <= sum; i++) {
			if (len[i] % 2 == 1) {
				fla = 0;
				break;
			}
			else if (len[i] % 4 == 2) {
				cc++;
			}
		}
		if (fla != 0 && cc <= H / 2) {
			cout << "Yes" << endl;
		}
		else
			cout << "No" << endl;

	}
	else if (H % 2 == 1 && W % 2 == 1) {
		for (i = 0; i <= sum; i++) {
			if (len[i] % 4 == 1) {
				cnt++;
			}
			else if (len[i] % 4 == 2) {
				cc++;
			}
			else if (len[i] % 4 == 3) {
				cnt1++;
			}
		}
		if (cnt + cnt1 == 1) {
			if (cnt == 1 && cc <= (W - 1) / 2 + (H - 1) / 2) {
				cout << "Yes" << endl;
			}
			else if (cnt1 == 1 && cc + 1 <= (W - 1) / 2 + (H - 1) / 2)
				cout << "Yes" << endl;
			else
				cout << "No" << endl;
		}
		else
			cout << "No" << endl;
	}





    return 0;
}



Measured memory_bytes: 256
from itertools import permutations

class Graph():  #non-directed
    def __init__(self, n, edge):
        self.n = n
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - 1].append((e[1] - 1, e[2]))
            self.graph[e[1] - 1].append((e[0] - 1, e[2]))

    def warshall_floyd(self, INF=10**18):
        dist = [[INF for j in range(self.n)] for i in range(self.n)]
        for i in range(self.n):
            dist[i][i] = 0
        for i in range(self.n):
            for j, cost in self.graph[i]:
                dist[i][j] = cost
        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][k] != INF and dist[k][j] != INF:
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        return dist

N, M, R = map(int, input().split())
T = list(map(int, input().split()))
E = [tuple(map(int, input().split())) for _ in range(M)]

G = Graph(N, E)
D = G.warshall_floyd()

ans = 10**18

for p in permutations(range(R)):
    dist = 0
    for i in range(R - 1):
        t1, t2 = T[p[i]], T[p[i + 1]]
        dist += D[t1 - 1][t2 - 1]
    ans = min(ans, dist)

print(ans)

Measured memory_bytes: 52184
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
void amin(ll &a, ll b){ a=min(a,b); }
void amax(ll &a, ll b){ a=max(a,b); }
void YES(){cout<<"YES\n";} void NO(){cout<<"NO\n";}
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
const ll INF = ll(1e18);
const int MOD = 998244353;

const bool DEBUG = 0;
const int MAXN = 3005;

int n;
ld a[MAXN];
ld dp[MAXN][MAXN];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin>>n;
	fore(i,1,n) cin>>a[i];
	setp(10);
	
	dp[0][0]=1;
	
	fore(i,1,n) fore(j,0,n)
	{
		dp[i][j]+=(j?dp[i-1][j-1]*a[i]:0) + dp[i-1][j]*(1-a[i]);
	}
	ld ans=0;
	fore(i,(n+1)/2, n) ans+=dp[n][i];
	cout<<ans<<'\n';
	
	return 0;
}


Measured memory_bytes: 144616
from itertools import permutations
from functools import reduce
from operator import mul


def solve(string):
    n, *xy = map(int, string.split())
    *xy, = zip(*[iter(xy)] * 2)
    return str(
        sum(
            sum(((xy[p0][0] - xy[p1][0])**2 + (xy[p0][1] - xy[p1][1])**2)**0.5
                for p0, p1 in zip(list(i),
                                  list(i)[1:]))
            for i in permutations(range(n), n)) / reduce(mul, range(1, n + 1)))


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n)+'\n'.join([input() for _ in range(n)])))


Measured memory_bytes: 3572
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        HashSet<Integer> set = new HashSet<>();
        boolean found = false;
        for (int i = 0; i < N; i++) {
            int A = scan.nextInt();
            if (set.contains(A)) {
                found = true;
                continue;
            }
            set.add(A);
        }
        String ans = found ? "NO" : "YES";
        System.out.println(ans);
    }
}


Measured memory_bytes: 100464
from collections import deque

k = int(input())

deq = deque()
for i in range(1, 10):
    deq.append(i)

for idx in range(k):
    ret = deq.popleft()
    # retの右に1つ付け加えてできるルンルン数を追加
    residue = ret % 10
    if residue != 0:
        deq.append(ret * 10 + residue - 1)
    
    deq.append(ret * 10 + residue)

    if residue != 9:
        deq.append(ret * 10 + residue + 1)

print(ret)


Measured memory_bytes: 18608
#include <iostream>
using namespace std;
int main() {
	int A,B,C,D,P;
	int X=0,Y=0;
	cin >> A >> B >> C >> D>> P;
	X=A*P;
	Y=B+(P-C)*D;
	int S=P-C;
	if(S<=0){
		Y=B;
	}
	if(X>Y){
		cout<< Y <<endl;
	}
	else {
		cout<< X << endl;
	}

	return 0;
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }



int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(25);

  int n;
  cin >> n;
  vector<string> s(n);
  rep(i, n) cin >> s[i];

  multiset<pair<int, int>> pos, neg;
  rep(i, n) {
    int f = 0, v = 0;
    rep(j, s[i].length()) {
      if (s[i][j] == '(') f++;
      else f--;
      chmin(v, f);
    }
    if (f >= 0) pos.insert({-v, f});
    else neg.insert({-(v - f), -f});
  }
  int f = 0;
  for (auto it = pos.begin(); it != pos.end(); it++) {
    pair<int, int> p = *it;
    if (f < p.first) {
      cout << "No\n";
      return 0;
    }
    else f += p.second;
  }
  int b = 0;
  for (auto it = neg.begin(); it != neg.end(); it++) {
    pair<int, int> p = *it;
    if (b < p.first) {
      cout << "No\n";
      return 0;
    }
    else b += p.second;
  }
  cout << (f == b ? "Yes" : "No") << '\n';



  




  
  return 0;
}

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

const double yb = 380000.0;

int main() {
  double ans = 0.0;
  int n; cin >> n;
  for (int i = 0; i < n; i++){
    double x; string s; cin >> x >> s;
    if(s == "JPY") ans += x;
    else ans += x * yb;
  }
  
  cout << fixed << setprecision(10) << ans;
}

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

long long int x;
int main(){
	scanf("%lld", &x);
	long long int ans = 0;
	for (int i = 1; i <= x; i++){
		ans += i;
		if (ans >= x){
			printf("%d\n", i);
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 256
/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>


using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
const string FILENAME = "input";
const int MAXN = 328;
const int Mod = 998244353;


int sum(const int &a, const int &b) {
	return (a + b >= Mod ? a + b - Mod: a + b);
}

int mul(const int &a, const int &b) {
	return (1LL * a * b) % Mod;
}

int powm(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) {
			res = mul(res, a);
		}
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}


int n;
int a[MAXN];
int dp[2][90001];
int dp1[2][90001];


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 //read(FILENAME);
	cin >> n;
	int sums = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		sums += a[i];
	}
	int bound = (sums - 1) / 2;
	int ans = powm(3, n);
	dp[0][0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= 90000; j++) {
			dp[1][j] = sum(dp[1][j], mul(dp[0][j], 2));
			if (j + a[i] <= 90000) {
				dp[1][j + a[i]] = sum(dp[1][j + a[i]], dp[0][j]);
			}
		}
		swap(dp[1], dp[0]);
		memset(dp[1], 0, sizeof(dp[1]));
	}
	dp1[0][0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= 90000; j++) {
			dp1[1][j] = sum(dp1[1][j], dp1[0][j]);
			if (j + a[i] <= 90000) {
				dp1[1][j + a[i]] = sum(dp1[1][j + a[i]], dp1[0][j]);
			}
		}
		swap(dp1[1], dp1[0]);
		memset(dp1[1], 0, sizeof(dp1[1]));
	}
	if (sums % 2 == 1) {
		for (int j = bound + 1; j <= 90000; j++) {
			ans = sum(ans, Mod - mul(dp[0][j], 3));
		}
	} else {
		for (int j = bound + 1; j <= 90000; j++) {
			ans = sum(ans, Mod - mul(dp[0][j], 3));
		}
		int k = mul(dp1[0][bound + 1], 3);
		ans = sum(ans, k);
	}
	cout << ans << '\n';
	return 0; 	
}

Measured memory_bytes: 1664
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		long min = 2;
		long max = 2;
		for(int i=N-1;i>=0;i--){
			long a = A[i];
			
			long l = ((min + a - 1)/ a) * a ;
			if(!InRange(l, min, max + 1)){
				Console.WriteLine(-1);
				return;
			}
			long r = (max / a) * a;
			if(!InRange(r, min, max + 1)){
				Console.WriteLine(-1);
				return;
			}
			
			min = l;
			max = r + (a - 1);
			
		}
		Console.WriteLine("{0} {1}",min,max);
		
	}
	
	bool InRange(long t, long l, long r){
		return l <= t && t < r;
	}
	int N;
	long[] A;
	public Sol(){
		N = ri();
		A = rla();
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


Measured memory_bytes: 27356
#include <bits/stdc++.h>
using namespace std;
#define rep(i,c) for(int i=0;i<c;++i)

bool yon(pair<string, int> c,pair<string, int> d){
  if(c.first!=d.first){
    return c.first<d.first;
  } 
  if(c.second!=d.second){
    return c.second>d.second;
  }else{
    return true;
  }
}
int  main(){
int a;
cin >> a;
 pair<pair<string,int>,int> b[110];
rep(i,a){
  string c;
  int d;
  cin >> c >> d;
  b[i]=make_pair(make_pair(c,-d),i);
}

sort(b,b+a);
rep(i,a){
cout << b[i].second+1 << endl;
}
return 0;
}

Measured memory_bytes: 256
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
  return int(readline())
r = I()
if r < 1200:
    print('ABC')
elif r < 2800:
    print('ARC')
else:
    print('AGC')


Measured memory_bytes: 10392
#include <bits/stdc++.h>
#define REP(i, n) for (ll i = 0; i < (ll)n; i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef vector<int > vecint;
typedef vector<ll > vecll;
typedef vector<vector<int > > vec2int;
typedef vector<bool > vecbool;
typedef vector<string > vecstr;
////////////////////////////////////////////////
int main()
{
  int n;
  cin >> n;
  int n3 = 3*n;
  priority_queue<int, vecint, greater<int> > q1;
  priority_queue<int> q2;

  vecint a(n3);
  vecll sum1(n + 1,0);// [0,i + n - 1]
  vecll sum2(n + 1,0);// [3n - i,3n] 0<= i <= n
  int tmp;
  REP(i,n3){
    cin >> tmp;
    a[i] = tmp;
    if(i < n){
      q1.push(tmp);
      sum1[0] += tmp;
    }else if(2*n <= i){
      q2.push(tmp);
      sum2[n] += tmp;
    }
  }
  //////initial

  /// sum1
  for(int k = n;k < 2*n; k ++){

    tmp = q1.top();q1.pop();
    if(tmp <= a[k]){
      // tmp remove (push a[k])
      q1.push(a[k]);
      sum1[k - n + 1] = sum1[k - n] + a[k] - tmp;
    }else{
      // tmp remain (deny a[k])
      q1.push(tmp);
      sum1[k - n + 1] = sum1[k - n];
    }
  }
  // REP(i,n + 1){
  //   cout << sum1[i] << endl;
  // }

  // sum2
  for(int k = 2*n - 1;k >= n; k --){
    tmp = q2.top();q2.pop();
    if(tmp >= a[k]){
      // tmp remove (push a[k])
      q2.push(a[k]);
      sum2[k - n] = sum2[k - n + 1] + a[k] - tmp;
    }else{
      // tmp remain (deny a[k])
      q2.push(tmp);
      sum2[k - n] = sum2[k - n + 1];
    }
  }
  

  ll ans = sum1[0] - sum2[0];
  REP(i, n + 1){
    ans = max(ans, sum1[i] - sum2[i]);
  }
  cout << ans << endl;
}



Measured memory_bytes: 4088
N, M = map(int, input().split(' '))
H = list(map(int, input().split(' ')))
edges = {i: [] for i in range(N)}
for _ in range(M):
    A, B = map(int, input().split(' '))
    edges[A - 1].append(B - 1)
    edges[B - 1].append(A - 1)

ans = 0
for i in range(N):
    flag = True
    for edge in edges[i]:
        if H[i] <= H[edge]:
            flag = False
            break
    ans += int(flag)
print(ans)

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

int main(){
  long n,kekka = 0,yaku2 = 0,yaku4 = 0,yaku14 = 0,yaku24 = 0,yaku74 = 0;
  cin >> n;
  long a[101],b[101] = {0};
  for(long i = 2;i <= 100;i++){
    a[i] = i;
  }
  for(long i = 2;i <= n;i++){
    for(long j = 2;j <= n;j++){
      while(a[j] % i == 0){
        a[j] /= i;
        b[i]++;
      }
    }
  }
  for(long i = 2;i <= n;i++){
    if(b[i] >= 74){
      yaku74++;yaku24++;yaku14++;yaku4++;yaku2++;
    }
    else if(b[i] >= 24){
      yaku24++;yaku14++;yaku4++;yaku2++;
    }
    else if(b[i] >= 14){
      yaku14++;yaku4++;yaku2++;
    }
    else if(b[i] >= 4){
      yaku4++;yaku2++;
    }
    else if(b[i] >= 2){
      yaku2++;
    }
  }
  kekka += yaku74 + yaku24*(yaku2 - 1) + yaku14*(yaku4 - 1) + yaku4*(yaku4 - 1)*(yaku2 - 2)/2;
  cout << kekka << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

constexpr int Mod = 998244353;
constexpr int mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;

template <typename T> constexpr bool chmax(T &a, const T b) {
    if(a >= b) return false;
    a = b;
    return true;
}
template <typename T> constexpr bool chmin(T &a, const T b) {
    if(a <= b) return false;
    a = b;
    return true;
}

/*-------------------------------------------*/

class UnionFind {
    vector<int> par, Size;
    vector<ll> omomi;

  public:
    UnionFind(int n, vector<ll> v) : par(n), Size(n), omomi(v) {
        rep(i, n) {
            par[i] = i;
            Size[i] = 1;
        }
    }

    int root(int x) {
        if(par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    bool same(int x, int y) { return root(x) == root(y); }

    void unite(int x, int y) {
        x = root(x);
        y = root(y);
        if(x == y) return;
        if(Size[x] > Size[y]) {
            Size[x] += Size[y];
            par[y] = x;
            omomi[x] += omomi[y];
        } else {
            Size[y] += Size[x];
            par[x] = y;
            omomi[y] += omomi[x];
        }
    }

    int size(int x) { return Size[root(x)]; }
    ll weight(int x) { return omomi[root(x)]; }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int n, m;
    cin >> n >> m;
    vector<ll> x(n);
    rep(i, n) cin >> x[i];
    UnionFind UF(n, x);
    struct Edge {
        int a, b, idx;
        ll y;
        Edge(int a, int b, ll y, int idx) : a(a), b(b), y(y), idx(idx) {}
    };
    struct Edge2 {
        int to, idx;
        ll cost;
        Edge2(int to, ll cost, int idx) : to(to), cost(cost), idx(idx) {}
    };
    vector<Edge> e;
    vector<vector<Edge2>> G(n);
    rep(i, m) {
        int a, b;
        ll y;
        cin >> a >> b >> y;
        a--;
        b--;
        e.push_back(Edge(a, b, y, i));
        G[a].push_back(Edge2(b, y, i));
        G[b].push_back(Edge2(a, y, i));
    }
    sort(ALL(e), [&](Edge a, Edge b) { return a.y < b.y; });
    vector<Edge> e2;
    for(Edge i : e) {
        UF.unite(i.a, i.b);
        if(UF.weight(i.a) >= i.y) e2.push_back(i);
    }
    sort(ALL(e2), [&](Edge a, Edge b) { return a.y > b.y; });
    vector<bool> use(m);
    for(Edge i : e2) {
        if(use[i.idx]) continue;
        queue<int> que;
        que.push(i.a);
        while(!que.empty()) {
            int v = que.front();
            que.pop();
            for(Edge2 j : G[v]) {
                if(j.cost <= i.y && !use[j.idx]) {
                    use[j.idx] = true;
                    que.push(j.to);
                }
            }
        }
    }
    int ans = 0;
    rep(i, m) ans += 1 - use[i];
    cout << ans << endl;

    return 0;
}

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

using namespace std;

int main(void){
	int a, b, c;
	scanf("%d %d %d", &a, &b, &c);
	int i, j, k;
	i = max(max(a, b), max(b, c));
	j = min(min(a, b), min(b, c));
	int max = i, min = j;
	if(max == a){
		a = -1;
	}else if(max == b){
		b = -1;
	}else if(max == c){
		c = -1;
	}
	if(min == a){
		a = -1;
	}else if(min == b){
		b = -1;
	}else if(min == c){
		c = -1;
	}

	if(a == -1 && b == -1) k = c;
	if(a == -1 && c == -1) k = b;
	if(b == -1 && c == -1) k = a;

	if((i-j-(i-k)) % 2 == 0){
		printf("%d\n", (i - k) + (i-j-(i-k))/2);
	}else{
		printf("%d\n", (i - k) + (int) ceil((double)(i-j-(i-k))/2) + 1);
	}
	
	return 0;
}

Measured memory_bytes: 256
a, b, c, x = [int(input()) for _ in range(4)]
cnt = 0
for i in range(min(a, int(x/500)) + 1):
    for j in range(min(b, int((x - 500 * i)/100)) + 1):
        k = (x - 500 * i - 100 * j)
        if k % 50 == 0 and 0 <= k / 50 <= c:
            cnt += 1
print(cnt)


Measured memory_bytes: 3060
n = int(input())
a = list(map(int,input().split()))
a.sort()
m = 10**9+7
if n%2 == 0:
  l = []
  for i in range(1,n//2+1):
    l.append(i*2-1)
    l.append(i*2-1)
  if a != l:
    print(0)
    exit()
  print(2**(n//2) %m)
else:
  l = [0]
  for i in range(1,n//2+1):
    l.append(i*2)
    l.append(i*2)
  if a != l:
    print(0)
    exit()
  print(2**(n//2) %m)

Measured memory_bytes: 14008
#include <stdio.h>
#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <cstdio>
#include <stack>
#include <vector>
#include <map>
#include <ctime>
#include <string.h>
#define inf 0x7fffffff
using namespace std;
//1232
int n,m,k,i,a,c,o[34],d,b,l[24],j[3333],dx[10]={0,1,-1,0,0,-1,-1,1,1},dy[10]={0,0,0,-1,1,1,-1,1,-1};
long long x,y,z;
stack<int> s;
struct P
{
    int x,y;
    long long z;
    bool operator<(const P &a)const
    {
        return y>a.y;
    }
};
 //map<int, int> p;
queue<P> q;
string r;
vector<P> v[1000100];
//vector<long long> ;
bool sdf(long long a,long long b){return a>b;}



int main()
{
    scanf("%d %d %d",&a,&b,&c);
    if(a%2||b%2||c%2)
    {
        puts("0");
        return 0;
    }
    if(a==b&&b==c)
    {
        puts("-1");
        return 0;
    }
    for(k=0;a%2==0&&b%2==0&&c%2==0;k++)
    {
        int n=a,m=b,i=c;
        a=(m+i)/2;
        b=(n+i)/2;
        c=(n+m)/2;
    }
    printf("%d",k);
    return 0;
}


Measured memory_bytes: 23680
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
using namespace std;
int dt[][2]= {{1,0},{-1,0},{0,1},{0,-1},{0,0}};
//typedef pair<int, int> P;
//priority_queue<int, vector<int>, greater<int> > q;
const int N=1e6+5;
int a[N];
int main()
{
   IOS;
   int n,m;
   cin >> n >> m;
   ll sum=0;
   for(int i=1;i<=m;i++){
       cin >> a[i];
       sum+=a[i];
   }
   if(sum>n)puts("-1");
   else cout<<n-sum;
}


Measured memory_bytes: 3648
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    H,W=map(int,input().split())
    print('#'*(W+2))
    for _ in range(H):
        print('#'+str(input())+'#')
        
    print('#'*(W+2))

    
resolve()

Measured memory_bytes: 38384
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int n;
long long ans;

int main()
{
    //freopen("1", "r", stdin);
    while (~scanf("%d", &n))
    {
        ans = 0;
        while (n--)
        {
            long long a, b;
            char ch;
            scanf("%lld %c %lld", &a, &ch, &b);
            if (ch == ')')
            {
                ans += b;
            }
            else
            {
                ans -= b;
            }
            if (ans) printf("No\n");
            else printf("Yes\n");
        }
    }
    return 0;
}

Measured memory_bytes: 1172
using System;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            string arg = Console.ReadLine();

            for(int i=0; i < 4; i++)
            {
                var x = arg.Substring(i, 1); //n文字目
                if(arg.Length - arg.Replace(x.ToString(), "").Length != 2)
                {
                    Console.Write("No");
                    return;
                }
            }
            Console.Write("Yes");

        }
    }
}


Measured memory_bytes: 11092