akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;
#define getbit(n, i) (((n) & (1LL << (i))) != 0)
#define setbit0(n, i) ((n) & (~(1LL << (i))))
#define setbit1(n, i) ((n) | (1LL << (i)))
#define togglebit(n, i) ((n) ^ (1LL << (i)))
char gap = 32;
template < typename T >
ostream& operator<<(ostream &os, const vector < T > &v) {
  os << '{';
  for (const auto &x: v) os << gap << x;
  return os << '}';
}
template < typename A, typename B >
ostream& operator<<(ostream &os, const pair < A, B > &p) {
  return os << '(' << p.first << gap << p.second << ')';
}

template < class T >
void read(T &x) {
  char c;
  for (c = getchar(); c < '0' || c > '9'; c = getchar());
  for (x = 0; c <= '9' && c >= '0'; c = getchar()) x = x * 10 + (c & 15);
}
#define ll long long
#define lll __int128_t
#define pb push_back
#define mp make_pair
typedef pair < int, int > ii;
typedef vector < ii > vii;
typedef vector < ll > vl;
typedef vector < int > vi;
typedef vector < vi > vvi;
typedef tree <
int,
null_type,
less < int >,
rb_tree_tag,
tree_order_statistics_node_update >
ordered_set;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll hashPrime = 1610612741;
ll dp[1001][1001];
ll mod=1000000007;
vector<string>Data;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  ll i,j,k,l,n,m;
  cin>>n>>m;
  vector<pair<ll,ll>>res;
  ll ini=1;
  ll fina=n;
  vector<ll>used(n+1,0);
  ll kola1=(m+1)/2;
  while(kola1--){
    used[ini]=1;used[fina]=1;
    res.pb({ini++,fina--});
  }
  m=m/2;
  ll cnt=2*m;
  while(m--){
    while(used[ini]==1) ini++;
    res.pb(make_pair(ini,ini+cnt));
    used[ini]=1;
    used[ini+cnt]=1;
    cnt-=2;
  }
  for(auto x:res) cout<<x.first<<" "<<x.second<<'\n';
}

Measured memory_bytes: 6604
#pragma GCC optimize("Ofast", "unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int k;
vector<int> d;

ll solve(ll n, ll x, ll m) {
	// dm[i] := d[i] mod m
	vector<ll> dm(k);
	for (int i = 0; i < k; ++i)
		dm[i] = d[i] % m;
	// a[n-1]を計算する
	// dm[i % k] = 0となるiの個数をカウントする
	ll a_lst = x;
	ll cnt = 0;
	for (int i = 0; i < k; ++i) {
		ll tmp = (n - 1) / k;
		if ((n - 1) % k > i) ++tmp;
		a_lst += dm[i] * tmp;
		if (dm[i] == 0)
			cnt += tmp;
	}
	// 答えを計算する
	return (n - 1) - (a_lst / m - x / m + cnt);
}

int main() {
	int q;
	cin >> k >> q;
	d.resize(k);
	for (int i = 0; i < k; ++i)
		cin >> d[i];
	while (q--) {
		ll n, x, m;
		cin >> n >> x >> m;
		cout << solve(n, x, m) << endl;
	}
	return 0;
}

Measured memory_bytes: 384
n=int(input())
line=input()
koko=line.split()
koko=map(int,koko)
koko=list(koko)
ans=dict.fromkeys(list(range(n+1)),0)
for val in koko:
     ans[val]=ans.get(val,0)+1
po=ans.pop(0)
for (k,v) in ans.items():
     print(v)

Measured memory_bytes: 42272
def gen_prime_decompositon(n):
    x = n
    d = 2
    cnt = 0
    while x % d == 0:
        x //= d
        cnt += 1
    if cnt != 0: yield cnt

    d = 3
    while d * d <= n:
        cnt = 0
        while x % d == 0:
            x //= d
            cnt += 1
        if cnt != 0: yield cnt
        d += 2

    if x > 1:
        yield 1


def main():
    from bisect import bisect_left
    from itertools import accumulate

    N = int(input())

    *acc, = accumulate(range(1, 40 + 1))

    ans = 0
    for cnt in gen_prime_decompositon(N):
        ans += bisect_left(acc, cnt + 1)  # acc上でcnt未満の個数=引ける回数

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9224
'''
.append(要素) リストに要素を追加
.extend(リスト) リストを連結する
.insert(場所,要素) 指定した場所に要素追加
del 配列名[場所]
-1で末尾で末尾から一つ前

sort()
sorted(reverse=true)

配列の初期化
配列名=[a]*n+[b]*m

Decimal()
'''

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
from functools import reduce
from operator import mul
from collections import Counter
import itertools
import fractions
import sys

n = stdin.readline().rstrip()
if n[-1] == '2' or n[-1] == '4' or n[-1] == '5' or n[-1] == '7' or n[-1] == '9':
    print('hon')
if n[-1] == '0' or n[-1] == '1' or n[-1] == '6' or n[-1] == '8':
    print('pon')
if n[-1] == '3':
    print('bon')


Measured memory_bytes: 72660
#include<bits/stdc++.h> //Ithea Myse Valgulious
namespace chtholly{
typedef long long ll;
#define re0 register int
#define rec register char
#define rel register ll
#define gc getchar
#define pc putchar
#define p32 pc(' ')
#define pl puts("")
/*By Citrus*/
inline int read(){
  int x=0,f=1;char c=gc();
  for (;!isdigit(c);c=gc()) f^=c=='-';
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return f?x:-x;
  }
template <typename mitsuha>
inline bool read(mitsuha &x){
  x=0;int f=1;char c=gc();
  for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';
  if (!~c) return 0;
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return x=f?x:-x,1;
  }
template <typename mitsuha>
inline int write(mitsuha x){
  if (!x) return 0&pc(48);
  if (x<0) x=-x,pc('-');
  int bit[20],i,p=0;
  for (;x;x/=10) bit[++p]=x%10;
  for (i=p;i;--i) pc(bit[i]+48);
  return 0;
  }
inline char fuhao(){
  char c=gc();
  for (;isspace(c);c=gc());
  return c;
  }
}using namespace chtholly;
using namespace std;

int main(){
int a=read(),b=read(),k=read();
for (int i=a;i<min(b+1,(a+k));++i){
  printf("%d\n",i);
  }
for (int i=b-k+1;i<=b;++i){
  if (i-a>=k) printf("%d\n",i);
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <tuple>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i>b;i--)
#define vint vector<int> 
#define vvint vector<vint>
#define CST(x) cout<<fixed<<setprecision(x)//小数点以下の桁数指定
#define ct(a) cout<<a<<endl
static const double pi = 3.141592653589793;
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int INF = 1e9+7;

int a[51], b[51], c[51], d[51];
int N, M, Q;
int ans;

void solve(int n, int p, vector<int>& V) {

	if (n == N) {
		int cur = 0;
		FOR(i, 0, Q) {
			if (V[b[i]] - V[a[i]] == c[i])cur += d[i];
		}
		ans = max(ans, cur);
		return;
	}

	for (int i = p; i <= M; i++) {
		vector<int> cp = V;
		cp.push_back(i);
		solve(n + 1, i,cp);
	}


}


int main(){
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	
	cin >> N >> M >> Q;
	FOR(i, 0, Q) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		a[i]--; b[i]--;
	}
	vector<int> v(0);
	solve(0, 1, v);
		cout << ans << endl;

	return 0;
}


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

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef long double ld;
typedef vector<ld> vd;
typedef bool bl;
typedef vector<bl> vb;
typedef vector<vl> mt;
typedef unordered_map<ll,unordered_map<ll,ll>> graph;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<string> vs;
typedef vector<vs> table;
typedef vector<vl> v2;
typedef vector<v2> v3;
typedef vector<v3> v4;


const ll e5 = 1 << 20;
const ll mods[] = {998244353, 1000000007, 1000000009};
const ll bases[] = {997, 1009, 1013};
// const ll mod = mods[0];
const ll e3 = 1 << 13;
const ll INF = 1ll << 50;

ll x[4], y[4];

int main(){
  cin >> x[0] >> y[0];
  cin >> x[1] >> y[1];
  for(ll i = 2;i < 4;i++){
    x[i] = x[i-1]-(y[i-1]-y[i-2]);
    y[i] = y[i-1]+(x[i-1]-x[i-2]);


  }
  cout << x[2] << " " << y[2] << " " << x[3] << " " << y[3] << endl;
}


Measured memory_bytes: 256
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m = map(int, input().split())
uf = UnionFind(n)
fr = []
# G = [[] for _ in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    uf.union(a,b)
    fr.append((a,b))
c = []
# tmp_s = set()
for i in range(n):
    c.append(uf.size(i))
    # c[i] = tuple(uf.members(i))
# print(c)
c = set(c)
c = list(c)
c.sort(reverse=1)
if len(c) == 1:
    print(c[0])
else:
    ans = c[1]
    ans += c[0]-c[1]
    print(ans)
# print(c)
# sc = set(c)
# sc = list(sc)
# lenc = []
# for ss in sc:
#     lenc.append(len(ss))
# lenc = set(lenc)
# lenc = list(lenc)
# lenc.sort(reverse=1)
# if len(lenc) == 1:
#     print(lenc[0])
# else:
#     ans = lenc[1]
#     ans += lenc[0]-lenc[1]
#     print(ans)






Measured memory_bytes: 107800
//include
//------------------------------------------
#include <bits/stdc++.h>
using namespace std;
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const long long INF = 1000000007;
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
// chmax chmin
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}

int main(void){
    int A,B; cin >> A >> B;
    string S; cin >> S;
    auto v = split(S, '-');
    if(v.size() != 2) cout << "No" << endl;
    else if(v[0].size() != A) cout << "No" << endl;
    else if(v[1].size() != B) cout << "No" << endl;
    else cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#![allow(unused_imports)]
use proconio::marker::*;
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        n: isize,
    }

    let res = solve(n);
    println!("{}", res);
}

fn solve(n: isize) -> isize {
    const MODN: isize = 1e9 as isize + 7;
    let res = powmod(10, n, MODN) - powmod(9, n, MODN) * 2 + powmod(8, n, MODN);
    let res = res % MODN;
    (res + MODN) % MODN
}

fn powmod(a: isize, b: isize, modn: isize) -> isize {
    let mut res = 1;
    for _ in 0..b {
        res = res * a % modn;
    }
    res
}


Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
using Int = int_fast64_t;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	Int k, q; cin >> k >> q;
	vector<Int> d(k);
	for(auto &i:d) cin >> i;
	while(q--){
		Int n, x, m; cin >> n >> x >> m;
		vector<Int> b(d);
		for(auto &i:b) i %= m;
		Int q = (n-1) / k;
		Int r = n-1 - k*q;
		Int ans = n-1;
		for(Int i=0; i<k; ++i)
			if(b[i] == 0)
				ans -= q + (i < r ? 1 : 0);
		Int c = x;
		for(Int i=0; i<k; ++i)
			c += b[i] * (q + (i < r ? 1 : 0));
		ans -= c / m - x / m;
		cout << ans << "\n";
	}
}

Measured memory_bytes: 384
module app;

import core.bitop;

import std.algorithm;
import std.array;
import std.bigint;
import std.conv;
import std.stdio;
import std.string;

struct Input
{
    string s,t;
    int a,b;
    string u;
}

void parseInput(T)(out Input input, T file)
{
	with (file) with (input)
	{
		auto ar = readln().strip().split();
		s = ar[0].to!string;
		t = ar[1].to!string;
		ar = readln().strip().split();
		a = ar[0].to!int;
		b = ar[1].to!int;
        u = readln().strip();
	}
}

struct Output
{
}

auto main2(Input* input)
{
    if (input.s == input.u)
        return (input.a - 1).to!string ~ " " ~ input.b.to!string;
    else
        return input.a.to!string ~ " " ~ (input.b - 1).to!string;
}

unittest { writeln("begin unittest"); }

unittest // example1
{
	string example =
`red blue
3 4
red`;
	Input input = void;
	parseExample(input, example);
	auto result = main2(&input);
	writeln(result);
	assert(result == "2 4");
}

unittest // example2
{
	string example =
`red blue
5 5
blue`;
	Input input = void;
	parseExample(input, example);
	auto result = main2(&input);
	writeln(result);
	assert(result == "5 4");
}

unittest { writeln("end unittest"); }

void parseExample(out Input input, string example)
{
	struct Adapter
	{
		string[] _lines;
		this(string input) { _lines = input.splitLines(); }
		string readln() { auto line = _lines[0]; _lines = _lines[1..$]; return line; }
	}
	parseInput(input, Adapter(example));
}

void main()
{
	Input input = void;
	parseInput(input, stdin);
	auto result = main2(&input);
	writeln(result);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
using P = pair<int,ll>;
using Graph= vector<vector<P>>; 
#define rep(i,n) for (ll i=0; i < (n); ++i)
#define rep2(i,n,m) for(ll i=n;i<=m;i++)
#define rep3(i,n,m) for(ll i=n;i>=m;i--)
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define mpa make_pair
const ll INF=1e18 ;
inline void chmax(ll& a,ll b){a=max(a,b);}
inline void chmin(ll& a,ll b){a=min(a,b);}

int main(){
  ll  n; cin>> n ;
  ll k=n-1 ;
  //n の約数
  vector<ll> a ;
  for(ll i=2;i*i<=n;i++){
    if(n%i==0) {
      a.pb(i) ; 
      if(i*i!=n) a.pb(n/i) ;
  }
  }
  ll ans=0 ;
  a.pb(n) ;
  ll nd=n  ;
  for(ll v:a){
    nd=n ;
    while(nd%v==0){
      nd/=v ;
    }
   if(nd%v==1) ans++ ;
   
  }
  //cout<<ans<<endl ;
  //n-1の約数
 
   for(ll i=2;i*i<=k;i++){
    if(k%i==0){
     ans+=2 ;
     if(i*i==k) ans-- ;
    }
   }
  if(n!=2) ans++ ;
  cout<<ans<<endl ;
  return 0;
  }

Measured memory_bytes: 3612
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
	ll n , k ,i , attack=0;
	cin>>n>>k;
	int h[n];
	for(i=0;i<n;i++)
		cin>>h[i];
	
	sort(h,h+n)	;
	
	for(i=0;i<n-k;i++)
		attack+=h[i];
	
	cout<<attack<<endl;	

		
	
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define _ ios::sync_with_stdio(false);cin.tie(0);
#define __ cout<<fixed;cout<<setprecision(10);
#define int long long

int32_t main() {
	_ __

#ifdef LOCAL_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	int n, x, t;
	cin >> n >> x >> t;
	int count = 0;
	while (n > 0) {
		n -= x;
		count += t;
	}
	cout << count << "\n";

#ifdef LOCAL_JUDGE
	cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s.\n";
#endif

	return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ll long long
//#define int long long
#define pb push_back
#define x first
#define ld long double
#define y second
#define mk(a,b) make_pair(a,b)
#define rr return 0
#define sqr(a) ((a)*(a))
#define all(a) a.begin(),a.end()

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
template<class value, class cmp = less<value> >
using ordered_set = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template<class value, class cmp = less_equal<value> >
using ordered_multiset = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template<class key, class value, class cmp = less<key> >
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

/// find_by_order()
/// order_of_key()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int randll(int l = INT_MIN, int r = INT_MAX) {
    return uniform_int_distribution<int>(l, r)(rng);
}
main()
{
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector <int> a(n);
    for (auto &i : a) cin >> i;
    sort(all(a));
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if (a[i] + a[j] > a[k] && a[i] != a[j] && a[i] != a[k] && a[j] != a[k]) ++ans;
            }
        }
    }
    cout << ans << '\n';
}


Measured memory_bytes: 3652
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
typedef long long ll;
int main(){
  int n, k;cin>>n>>k;
  vector<int> l(n);
  for(int i=0;i<n;i++)cin>>l.at(i);
  sort(l.begin(), l.end(), greater<int>());
  int ans=0;
  for(int i=0;i<k;i++)ans+=l.at(i);
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int N;
int a[100000];

int main(){
    cin >> N;
    for(int i=0;i<N;i++) cin >> a[i];
    int x,y;
    x = y = 0;
    for(int i=0;i<N;i++){
        if(a[i] % 4 == 0) x++;
        if(a[i] % 2 == 1) y++;
    }
    if(x >= y){
        cout << "Yes" << endl;
        return 0; 
    }
    if(x+1 < y){
        cout << "No" << endl;
        return 0;
    }
    if(x + y == N){
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const int mod = 1e9+7;
ll qpow(ll a,ll b){ll res=1;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

int main()
{
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    bool ok = true;
    while(1)
    {
        c-=b;
        if(c<=0)break;
        a-=d;
        if(a<=0){
            ok=false;
            break;
        }
    }
    if(ok)printf("Yes\n");
    else printf("No\n");
    return 0;
}


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

using namespace std;

int SolveDaruma(const int n, const vector<int> &w) {
    vector<vector<int>> s(n, vector<int>(n));

    for (int l = 0; l + 1 < n; ++l)
        if (abs(w[l] - w[l + 1]) <= 1)
            s[l][l + 1] = 2;

    for (int i = 3; i <= n; ++i)
        for (int l = 0; l + i <= n; ++l) {
            const int r = l + i - 1;

            if (abs(w[l] - w[r]) <= 1 && s[l + 1][r - 1] == i - 2) {
                s[l][r] = i;
                continue;
            }

            for (int m = l + 1; m <= r; ++m)
                s[l][r] = max(s[l][r], s[l][m - 1] + s[m][r]);
        }

    return s[0][n - 1];
}

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

    int n;

    while (cin >> n, n) {
        vector<int> w(n);
        for (auto &x : w) cin >> x;

        cout << SolveDaruma(n, w) << '\n';
    }

    return 0;
}



Measured memory_bytes: 3324
N = int(input())
a = [int(x) for x in input().split()]
a_order = sorted(a, reverse=True)
alice, bob = 0, 0

for i in range(N):
  if i % 2 == 0:
    alice += a_order[i]
  else:
    bob += a_order[i]
    
print(alice-bob)
    

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

bool se(int key, vector<long> &p, vector<bool> &q, vector<map<int, long>> &r){
    bool flag=true;
    for(auto itr=r[key].begin(); itr!=r[key].end(); ++itr){
        if(q[itr->first]){
            q[itr->first]=false;
            p[itr->first]=p[key]+itr->second;
            flag &= se(itr->first, p, q, r);
        }
        else flag &= p[itr->first]==p[key]+itr->second;
    }
    return flag;
}

int main() {
	int N, M; cin >> N >> M;
	vector<long> loc(N+1, 0);
	vector<bool> ch(N+1, true);
	vector<map<int, long>> v(N+1);
	for(int i=0; i<M; ++i){
	    int L, R;
	    long D;
	    cin >> L >> R >> D;
	    v[L][R]=D;
	    v[R][L]=-D;
	}
	bool ans=true;
	for(int i=1; i<=N; ++i){
	    if(ch[i]) ans &= se(i, loc, ch, v);
	}
	if(ans){
	    long mn=1e10, mx=-1e10;
	    for(int i=1; i<=N; ++i){
	        if(!ch[i]){
	            mn=min(mn, loc[i]);
	            mx=max(mx, loc[i]);
	        }
	    }
	    cout << (mx-mn<=1e9 ? "Yes" : "No") << endl;
	}
	else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 35456
#include <bits/stdc++.h>
using namespace std;
long long c,x[100010],v[100010],A[100010],B[100010];
int n,i;
int main()
{
  scanf("%d%lld",&n,&c);
  for(i=1; i<=n; i++)
    scanf("%lld%lld",&x[i],&v[i]);	
  for(i=1; i<=n; i++)
    A[i]=A[i-1]+v[i]-x[i]+x[i-1];
  x[n+1]=c;
  for(i=n; i>=1; i--)
    B[i]=B[i+1]+v[i]-x[i+1]+x[i];
  for(i=2; i<=n; i++)
    A[i]=max(A[i],A[i-1]);
  for(i=n-1; i>=1; i--)
    B[i]=max(B[i+1],B[i]);
  long long ans=0;
  for(i=1; i<=n; i++)
    {
      ans=max(ans,A[i]-x[i]+B[i+1]);
      ans=max(ans,B[i]-c+x[i]+A[i-1]);
      ans=max(ans,max(A[i],B[i]));
    }
  printf("%lld\n",ans);
  //ll!!!!!!!!!!!!!!!!
  return 0;
}

Measured memory_bytes: 3328
import java.util.*;
import java.io.*;

public class Main {
	private static void solve(){
	//Implement solution here.
		int a = ni();
		int b = ni();
		int c = ni();
		System.out.println(Math.max(c - a + b , 0));
	}

    //Switch input source (stdin/file)
	private static BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args){
        String debugDataPath = System.getenv("DD_PATH");        
        if(debugDataPath != null){
            try{
            	br = new BufferedReader(new InputStreamReader(new FileInputStream(new File(debugDataPath))));
            }catch(Exception e){
                throw new RuntimeException(e);
            }
        } 
        solve();
	}

    //Input read utility
	private static StringTokenizer tokenizer = null;
	public static String next() {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}
    //Get next single int
	private static int ni() {
		return Integer.parseInt(next());
	}
    //Get next single long
	private static long nl() {
		return Long.parseLong(next());
	}
    //Get next single double
	private static double nd() {
		return Double.parseDouble(next());
	}
    //Get next int array from one line
	private static int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}
	//Get next char array from one line
	private static char[] ns() {
		return next().toCharArray();
	}
    //Get next long array from one line
	private static long[] nal(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nl();
		return a;
	}
}

Measured memory_bytes: 23124
#include <bits/stdc++.h>
#include <numeric>
typedef long long ll;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;

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

    string S, T;
    cin >> S >> T;
    
    bool res = true;
    map<char, char> StoT, TtoS;

    rep(i, 0, S.size()) {
        char s = S[i], t = T[i];
        if (StoT.count(s) > 0 and StoT[s] != t) res = false;
        if (TtoS.count(t) > 0 and TtoS[t] != s) res = false;
        StoT[s] = t;
        TtoS[t] = s;
    }

    cout << (res ? "Yes" : "No") << "\n";
}

Measured memory_bytes: 916
#include <iostream>

using namespace std;

int main(){
  int N, tmp, ans=0;
  cin >> N;
  int B[N-1];
  for(int i=0; i<N-1; i++) cin >> B[i];
  for(int i=0; i<N-1; i++){
    if(i==0){
      ans += B[i];
    }else{
      ans += min(B[i-1], B[i]);
    }
  }
  ans += B[N-2];
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
from sys import stdin

a = []
sum = 0

n = int(stdin.readline().rstrip())
a = [int(y) for y in stdin.readline().rstrip().split()]

for i in range(n) :
    sum = sum + a[i]

ave = sum / n
tmp = abs(a[0] - ave)
ans = 0

for i in range(n) :
    if (abs(a[i] - ave) < tmp ) and ( a[ans] is not a[i]):
        ans = i
        tmp = abs(a[i] - ave)
        
print(ans)


Measured memory_bytes: 3064
#include <stdio.h>
#include <algorithm>
using namespace std;
int n, m, t, i, j, k;
long long p[100005], x=1000000;
struct AB{
	int a, b, i;
	bool operator < (const AB &A) const{
		if(a != A.a) return a < A.a;
		return b < A.b;
	}
} d[100005];
int main(){
	scanf("%d%d", &m, &n);
	for(i=1; i<=n; i++){
		scanf("%d%d", &d[i].a, &d[i].b);
		d[i].i = i; 
	}
	sort(d+1, d+n+1);
	for(i=1; i<=n; i++){
		if(d[i].a != d[i-1].a) j = 0;
		p[d[i].i] = d[i].a * x + (++j);
	}
	for(i=1; i<=n; i++){
		printf("%012lld\n", p[i]);
	}
	return 0;
}

Measured memory_bytes: 3328
object Main {
  val Suits = Array('S', 'H', 'C', 'D')

  def main(args: Array[String]): Unit = {
    val scanner = new java.util.Scanner(System.in)
    val n = scanner.nextInt()

    val deck = Array.ofDim[Boolean](Suits.length, 13)

    Iterator.from(0, 1)
      .takeWhile(_ < n)
      .map(_ => (scanner.next(), scanner.nextInt() - 1))
      .foreach {
        case ("S", rank) => deck(0)(rank) = true
        case ("H", rank) => deck(1)(rank) = true
        case ("C", rank) => deck(2)(rank) = true
        case ("D", rank) => deck(3)(rank) = true
        case _ =>
      }

    deck
      .zipWithIndex
      .flatMap { case (cards, s) =>
        cards
          .zipWithIndex
          .collect { case (false, i) => i }
          .map(i => s"${Suits(s)} ${i + 1}")(collection.breakOut)
      }
      .foreach(println)
  }
}

Measured memory_bytes: 45468
import sys

def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def S(): return sys.stdin.readline().rstrip()

N,Z,W = map(int,S().split())
a = LI()

if N == 1:
    print(abs(a[0]-W))
else:
    print(max(abs(a[-1]-W),abs(a[-1]-a[-2])))

Measured memory_bytes: 64160
#include<bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
using LL = long long;
const LL LINF = 1e18;
using namespace std;
#define COUT(v) cout<<(v)<<endl
#define CIN(n)  int(n);cin >> (n)
#define YES(n) cout<<((n)? "YES" : "NO")<<endl
#define Yes(n) cout<<((n)? "Yes" : "No")<<endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) <<endl

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)

#define FOREACH(x,a) for(auto& (x) : (a) )

#define ALL(obj) (obj).begin(),(obj).end()

#define P pair<int,int>
#define I vector<int>
#define S set<int>
#define pb(v) push_back(v)
#define V vector
#define rt return
#define rmsame(a) sort(ALL(a)),a.erase(unique(ALL(a)), a.end())
class Edge{
public:
    int from,to,value;
    Edge(int a,int b,int c){
        from = a;
        to = b;
        value = c;
    }
    Edge(int a,int b){
        from = a;
        to = b;
    }
};
int main(){
    CIN(A);CIN(B);CIN(X);
    YES(A+B>=X&&X>=A);
    return 0;
}


Measured memory_bytes: 256
import copy

n, k = map(int,input().split())
a = [0] + list(map(int,input().split()))

dist = [-1] * (n+1)
dist[1] = 0

cn = 1
d = 0
cycle = 0
while True:
    d += 1
    nn = a[cn]
    if d == k:
        ans = nn
        break
    if dist[nn] == -1:
        dist[nn] = copy.deepcopy(d)
    elif cycle == 0:
        cycle = d - dist[nn]
        k = (k - d) % cycle + d
    if d == k:
        ans = nn
        break
    cn = nn

print(ans)

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

typedef long long LL;

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()
const int IINF = 1e9;
const LL LINF = 1e18;
const LL mod = 1e9+7;

int main() {
    int N;
    cin >> N;
    LL res = 0;
    REP(i, N + 1) {
        if(i%3 != 0 && i%5 != 0) {
            res += i;
        }
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 3632
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

answer = 0
for i in range(N):
    answer += b[a[i]-1]
    if i > 0 and a[i] == a[i-1]+1:
        answer += c[a[i-1]-1]
print(answer)

Measured memory_bytes: 3064
sa, sb, sc = [input() for i in range(3)]
sa, sb, sc = list(sa),list(sb),list(sc)

i = sa.pop(0)

while True : 
    if i =='a':
        if len(sa) ==0:
            print("A")
            exit()    
        i = sa.pop(0)

    if i =='b':
        if len(sb) ==0:
            print('B')
            exit()    
        i = sb.pop(0)

    if i =='c':
        if len(sc) ==0:
            print('C')
            exit()    
        i = sc.pop(0)
        

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;

int main() {
    char s[26 + 1] = {};
    cin >> s;

    size_t k = strlen(s);
    sort(s, s + k);

    cout << (s + k == unique(s, s + k) ? "yes" : "no") << endl;

    return 0;
}

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

void fnInput(vector<vector<int>> &rvvnAdjcy)
{
  int nMaxSiz;
  cin >> nMaxSiz;

  rvvnAdjcy.resize(nMaxSiz + 1, vector<int>(nMaxSiz + 1, 0));
  for (int i = 0; i < nMaxSiz; i++)
  {
    int nx, nSecSiz;
    cin >> nx >> nSecSiz;
    for (int j = 0; j < nSecSiz; j++)
    {
      int ny;
      cin >> ny;
      rvvnAdjcy[nx][ny] = 1;
    }
  }
}

void fnResult(const vector<vector<int>> &cnrvvnAdjcy)
{
  for (int i = 1; i < cnrvvnAdjcy.size(); i++)
  {
    for (int j = 1; j < cnrvvnAdjcy[i].size(); j++)
    {
      if (j != 1) cout << " ";
      cout << cnrvvnAdjcy[i][j];
    }
    cout << endl;
  }
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  vector<vector<int>> vvnAdjcy;

  fnInput(vvnAdjcy);
  fnResult(vvnAdjcy);

  return 0;
}

Measured memory_bytes: 3168
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

int main(void)
{
	int n;
	scanf("%d",&n);
	ll ans=0;
	for(int i=1; i<=n; ++i)
	{
		if(i%3 && i%5) ans += i;
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 3844
//https://atcoder.jp/contests/abc144/tasks/abc144_b
#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;
#define FOR(i,a,b) for(int64_t i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
int main() {
    ll N; cin>>N;
    FOR(i,1,9+1){
        FOR(j,1,9+1){
            if(i*j==N) {cout<<"Yes"<<endl;return 0;}
        }
    }
    cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
  int m, f, r;
  cin >> m >> f >> r;
  while (m != -1 || f != -1 || r != -1) {
    int sum = m + f;
    if (m == -1 || f == -1 || sum < 30) {
      cout << "F" << endl;
    } else {
      if (sum >= 80) {
        cout << "A" << endl;
      } else if (sum >= 65) {
        cout << "B" << endl;
      } else if (sum >= 50) {
        cout << "C" << endl;
      } else {
        if (r >= 50) {
          cout << "C" << endl;
        } else {
          cout << "D" << endl;
        }
      }
    }
    cin >> m >> f >> r;
  }
}


Measured memory_bytes: 3084
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    A = list(map(int, input().split())) #1行ベクトル
    B = tuple(map(int, input().split()))
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    cnt=0
    for i in range(N):
        a=A[i];b=B[i]
        if b>a:
            cnt+=min(b,a+A[i+1])
            A[i]=0
            A[i+1]=max(0,A[i+1]-(b-a))
            
        else:
            A[i]=a-b
            cnt+=b
        
    print(cnt)




if __name__ == "__main__":
    main()

Measured memory_bytes: 103176
N = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
abs_xy = list()

for i in range(N):
    abs_xy.append(abs(x[i] - y[i]))

abs_xy_2 = [abs_xy[i] ** 2 for i in range(N)]
abs_xy_3 = [abs_xy[i] ** 3 for i in range(N)]

print(sum(abs_xy))
print(sum(abs_xy_2) ** (1 / 2))
print(sum(abs_xy_3) ** (1 / 3))
print(max(abs_xy))


Measured memory_bytes: 5648
H, W, N = map(int, raw_input().split())
D = dict()

for i in range(N):
    a, b = map(int, raw_input().split())
    for a_add in [-1, 0, 1]:
        for b_add in [-1, 0, 1]:
            c = a + a_add
            d = b + b_add
            if c-1 in range(1, H-1) and d-1 in range(1, W-1):
                if D.has_key(str([c, d])):
                    D[str([c, d])] += 1
                else:
                    D[str([c, d])] = 1

res_list = [0]*10
for s in D.keys():
    res_list[D[s]] += 1

res_list[0] = (H-2) * (W-2) - sum(res_list)

for i in range(10):
    print res_list[i]

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

using namespace std;

#define ll long long

int water(vector<int> v) {
	if (v.size() == 0) return 0;
	int c = *min_element(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++)
		v[i] -= c;
	vector<int> nv(0);
	for (int i = 0; i < v.size(); i++) {
		if (v[i] == 0) {
			c += water(nv);
			nv.clear();
			continue;
		}
		nv.push_back(v[i]);
	}
	c += water(nv);
	return c;
}

int main() {
	int N;
	cin >> N;
	vector<int> h(N);
	for (int i = 0; i < N; i++)
		cin >> h[i];
	cout << water(h) << endl;
	return 0;
}

Measured memory_bytes: 256
//------------------------------>> tsukasa_diary's template <<------------------------------//
#include <bits/stdc++.h>
using namespace std;

#define for_(i,a,b) for(int i=(a);i<(b);++i)
#define allof(a) (a).begin(),(a).end()
using lint = long long;
template< typename T > using Vec = vector< T >;

template< typename T > bool inRange(T x, T lb, T ub) { return lb <= x && x < ub; }
template< typename T > bool inRange(T x, T y, T lb, T ub) { return in_range(x, lb, ub) && in_range(y, lb, ub); }
template< typename T > void modAdd(T& a, T b, T mod) { a = (a + b + mod) % mod; }
template< typename T > void modMul(T& a, T b, T mod) { a = (a * b) % mod; }
template< typename T > void minUpdate(T& a, T b) { a = min(a, b); }
template< typename T > void maxUpdate(T& a, T b) { a = max(a, b); }
inline int bitCount(int x) { return __builtin_popcount(x); }
inline int bitCount(lint x) { return __builtin_popcountll(x); }

const int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};
const int Dx[8] = {0,1,1,1,0,-1,-1,-1}, Dy[8] = {-1,-1,0,1,1,1,0,-1};
const double PI = acos(-1);

//--------------8---------------->> coding space <<-----------------8-------------//



int main() {
	int N;
	cin >> N;
	
	Vec< int > A(N), B(N);
	for (int i=0; i<N; ++i) cin >> A[i] >> B[i];
	
	Vec< int > order(N);
	iota(allof(order), 0);
	
	sort(allof(order), [&](int i, int j) {
		return B[i] == B[j] ? A[i] > A[j] : B[i] > B[j];
	});
	
	int cur = *max_element(allof(B));
	for (int i : order) {
		if (cur <= B[i]) {
			cur -= A[i];
		}
		else {
			cur = B[i] - A[i];
		}
	}
	puts(cur >= 0 ? "Yes" : "No");
}
//--------------8---------------->> coding space <<-----------------8-------------//

Measured memory_bytes: 2560
#include<iostream>
#include<string>
using namespace std;
int alphabet[100];
bool check = true;
int main() {
	string w;
	cin >> w;
	for (int i = 0; i < 100; i++)alphabet[i] = 1;
	for (int i = 0; i < w.size(); i++) {
		int tmp = w[i] - 'a';
		alphabet[tmp] *= -1;
	}
	for (int i = 0; i < 100; i++){
		if (alphabet[i] == -1)check = false;
 
	}
	if (check) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int n,m,cnt[31] = {},tmp,k[31],ans = 0;
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        cin >> k[i];
        for(int j = 1;j <= k[i];j++){
            cin >> tmp;
            cnt[tmp]++;
        }
    }
    for(int i = 1;i <= 30;i++){
        if(cnt[i] == n) ans++;
    }
    cout << ans << endl;
    return 0;
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N,M,P;
ll from[2500],to[2500];

vector<pair<int,int>> E[3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>P;
	FOR(i,M) {
		cin>>x>>y>>r;
		E[x-1].push_back({y-1,r});
	}
	
	FOR(i,N) from[i]=-(1LL<<60);
	from[0]=0;
	ll ma=-1LL<<60;
	FOR(i,10000) {
		FOR(j,N) to[j]=from[j];
		FOR(x,N) if(from[x]>-(1LL<<60)) FORR(e,E[x]) {
			to[e.first]=max(to[e.first],from[x]+e.second-P);
			if(i>=5100&&to[e.first]>from[e.first]) to[e.first]=1LL<<60;
		}
		
		ma=max(ma,to[N-1]);
		swap(from,to);
	}
	ma=max(ma,0LL);
	if(ma>=1LL<<59) ma=-1;
	cout<<ma<<endl;
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 512
N,M=map(int,input().split())
HList=list(map(int,input().split()))
ans=[i for i in range(1,N+1)]
for i in range(M):
    A,B=map(int,input().split())
    if HList[A-1]==HList[B-1]:
        ans[A-1]=0
        ans[B-1]=0
    elif HList[A-1]>HList[B-1]:
        ans[B-1]=0
    else:
        ans[A-1]=0
print(N-ans.count(0))


Measured memory_bytes: 20124
#include <stdio.h>
#include <math.h>

int main(void) {
  int n, h[100001], dp[100001];
  dp[0] = 0;
  scanf("%d", &n);
  
  for (int i = 0; i < n; i++) {
    scanf("%d", &h[i]);
  }

  for (int i = 1; i < n; i++) dp[i]=1E9;

  for (int i = 0; i < n; i++) {
    dp[i + 1] = fmin( dp[i + 1], dp[i] + abs(h[i] - h[i + 1]) );
    dp[i + 2] = fmin( dp[i + 2], dp[i] + abs(h[i] - h[i + 2]) );
  }
  printf("%d", dp[n - 1]);

  return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
 
// i<j
// j-i = a[i]+a[j]
// a[i]+i = j-a[j]
 
int main() {
  int n,m,a;
  cin >> n >> m;
  int sum = 0;
  
  rep(i,m){
    cin >> a; 
    sum += a;
  }
  
  int result = n -sum;
  if (result >= 0) cout << result << endl;
  else cout << -1 << endl;
}

Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100;
int n;
long long x[maxn], y[maxn];

map < pair < int, int >, int > apt;
int main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for(int i = 0;i < n;++i)cin >> x[i] >> y[i];
	for(int i = 0;i < n;++i){
		for(int j = i + 1;j < n;++j){
			++apt[{x[i] - x[j], y[i] - y[j]}];
			++apt[{x[j] - x[i], y[j] - y[i]}];
		}
	}
	int max_v = 0;
	for(auto &i : apt)max_v = max(max_v, i.second);
	cout << n - max_v << '\n';
}


Measured memory_bytes: 384
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {
	var n int
	var abc [100001][3]int
	var dp [100001][3]int

	fmt.Scanf("%d", &n)

	for i := 0; i < n; i++ {
		for j := 0; j < 3; j++ {
			fmt.Scanf("%d", &abc[i][j])
		}
	}

	for i := 0; i < 3; i++ {
		dp[0][i] = abc[0][i]
	}

	for i := 0; i < n; i++ {
		for j := 0; j < 3; j++ {
			if j == 0 {
				dp[i+1][0] = Max(dp[i][1], dp[i][2]) + abc[i+1][0]
			} else if j == 1 {
				dp[i+1][1] = Max(dp[i][0], dp[i][2]) + abc[i+1][1]
			} else {
				dp[i+1][2] = Max(dp[i][0], dp[i][1]) + abc[i+1][2]
			}
		}
	}
	ans := 0
	for i := 0; i < 3; i++ {
		ans = Max(ans, dp[n-1][i])
	}

	fmt.Println(ans)
}

func NextInt() string {
	sc.Scan()
	return sc.Text()
}

func NextLineInt() []int {
	lineString := strings.Split(NextInt(), " ")
	var lineInt = make([]int, len(lineString))
	for i := range lineString {
		lineInt[i], _ = strconv.Atoi(lineString[i])
	}
	return lineInt
}

func Bool2Int(b bool) int {
	if b {
		return 1
	} else {
		return 0
	}
}

func Abs(v int) int {
	if v < 0 {
		return -v
	}
	return v
}

func Min(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

func Max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func Distance(a, b int) int {
	return Abs(a - b)
}


Measured memory_bytes: 7936
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define MN 111111
int N,z;
int s[MN],A[MN];
signed main(){
    cin>>N>>z;N--;
    int h=0,a;
    char c;
    rep(i,N){
        cin>>c>>a;
        s[i]=(c=='+')?1:-1;
        A[i]=a;
        h+=a*s[i];
    }

    int ans=h,l=0,m=0;
    for(int i=N-1;i>=0;i--){
        l+=A[i];
        h-=A[i]*s[i];
        if(s[i]<0){
            ans=max(ans,h-l+m);
            m+=l;
            l=0;
        }
    }
    cout<<ans+z<<endl;
    return 0;
}


Measured memory_bytes: 1920
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <iomanip>
#include <cmath>
#include <boost/multiprecision/cpp_int.hpp>
#include <map>

using namespace std;
using ll = long long;
namespace mp = boost::multiprecision;

int main()
{
    // 整数の入力
    ll H,W,N;
    cin >> H >>W >> N;
    ll max_counts = max(H,W);
    cout << (N + max_counts - 1)/max_counts << endl;

    return 0;
}

Measured memory_bytes: 256
def gcd(a, b):
  while b:
    a, b = b, a%b
  return a

def lcm(a, b):
  return a*b // gcd(a, b)

N = int(input())
T = [int(input()) for _ in range(N)]

ans = 1
for t in T:
  ans = lcm(ans, t)
  
print(ans)  



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

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

using namespace std;

int main(){
	int n; cin>>n;
	int ans=100;
	rep(i,n){
		int a; cin>>a;
		int cnt=0;
		while(a%2==0) a/=2, cnt++;
		ans=min(ans,cnt);
	}
	cout<<ans<<endl;

	return 0;
}


Measured memory_bytes: 256
N, K = map(int, input().split())
p = [(int(x)+1)/2 for x in input().split()]

result = []
sub_total = sum(p[0:K])
result.append(sub_total)

for i in range(1, N-K+1):
    sub_total = sub_total - p[i-1] + p[i+K-1]
    result.append(sub_total)

print(max(result))


Measured memory_bytes: 23524
#include<iostream>
using namespace std;
int n,cnt;
int a[10000];
int main()
{
  cin >> n;
  for (int i = 0; i < n;i++)
  {
    cin >> a[i];
    for(int j=0;;j++)
    {
      if(a[i]%2==0)
      {
        a[i] /= 2;
        cnt++;
      }
      else
        break;
    }
  }
  cout << cnt << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
string s;
int n,k,c;
vector<int>v1,v2;
int main()
{
	cin>>n>>k>>c>>s;
	for(int i=0;i<n;i++)
	{
		if(s[i]=='x')
		{
			continue;
		}
		v1.push_back(i);
		i+=c;
	}
	for(int i=n-1;i>=0;i--)
	{
		if(s[i]=='x')
		{
			continue;
		}
		v2.push_back(i);
		i-=c;
	}
	for(int i=0;i<k;i++)
	{
		if(v1[i]==v2[k-i-1])
		{
			cout<<v1[i]+1<<endl;
		}
	}
	return 0;
}

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

int main()
{
	long long a,b,c,k;
	cin>>a>>b>>c>>k;
	int sum=0;
	if(k<=a)
		sum+=k;
	else
	{
		k-=a;
		sum+=a;
		if(k<=b)
			;
		k-=b;
		if(k<=c)
			sum-=k;
	}
	cout<<sum;

	return 0;
}

Measured memory_bytes: 3636
import java.util.Scanner;

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

		int N = Integer.parseInt(s.next());
		int M = Integer.parseInt(s.next());
		int C = Integer.parseInt(s.next());

		int[][] pro = new int[N + 1][M];
		for (int n = 0; n <= N; n++) {
			for (int m = 0; m < M; m++) {
				pro[n][m] = Integer.parseInt(s.next());
			}
		}

		int counts = 0;
		for (int n = 1; n <= N; n++) {
			int cra = 0;
			for (int m = 0; m < M; m++) {
				cra += pro[n][m] * pro[0][m];
			}
			if (cra + C > 0) {
				counts++;
			}
		}
		System.out.println(counts);
	}
}

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

int main(int argc, char const *argv[])
{
	int a,b;
	cin >> a >> b;
	int c,d;
	c = a*b;
	d = c % 2;
	if (d == 1)
	{
		cout << "Odd" << endl;
		/* code */
	}
	else cout << "Even" << endl;
	return 0;
}

Measured memory_bytes: 256