akhauriyash/Code-Regression huggingface dataset:
n, c = map(int, input().split())
stc = []
for _ in range(n):
  stc.append(tuple(map(int, input().split())))

sm = [0 for _ in range(2 * (pow(10, 5) + 1))]
for _c in range(c):
  tt = [0 for _ in range(2 * (pow(10, 5) + 1))]
  for s, t, c in stc:
    if c == _c + 1:
      tt[s * 2 - 1] += 1
      tt[t * 2] -= 1
  for i in range(1, len(tt)):
    tt[i] += tt[i-1]
  for i in range(len(sm)):
    if tt[i] > 0:
      sm[i] += 1

print(max(sm))


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

using namespace std;

int main()
{
    int x;
    int a;
    int b;

    cin >> x;
    a = x / 500;
    b = x % 500;
    b = b / 5;
    cout << ((a * 1000) + (b * 5)) << endl;
    return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>

int main()
{
  int N, M, cmp, i, j, key = 0;
  char U[ 260 ][ 15 ], T[ 260 ][ 15 ];

  scanf( "%d", &N );
  for( i = 0; i < N; i++ ){
    scanf( "%s", &U[ i ] );
  }

  scanf( "%d", &M );
  for( i = 0; i < M; i++ ){
    scanf( "%s", &T[ i ] );

    for( j = 0; j < N; j++ ){
      cmp = strcmp( U[ j ], T[ i ] );
      if( cmp == 0 ){
	if( key == 0 ){
	  printf("Opened by %s\n", U[ j ] );
	  key = 1;
	}

	else{
	  printf( "Closed by %s\n", U[ j ] );
	  key = 0;
	}
	
	break;	
      }

      if( j == N -1 ) printf( "Unknown %s\n", T[ i ] );
    }   
  }

  return 0;

}

Measured memory_bytes: 1832
#include <atcoder/all>
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
	int n, d;
	cin >> n >> d;
	atcoder::two_sat t(n);
	vector<int> x(n), y(n);
	rep(i, n) cin >> x[i] >> y[i];
	rep(i, n) for (int j = i + 1; j < n; ++j) {
		if (abs(x[i] - x[j]) < d) {
			t.add_clause(i, true, j, true);
		}
		if (abs(x[i] - y[j]) < d) {
			t.add_clause(i, true, j, false);
		}
		if (abs(y[i] - x[j]) < d) {
			t.add_clause(i, false, j, true);
		}
		if (abs(y[i] - y[j]) < d) {
			t.add_clause(i, false, j, false);
		}
	}
	if (t.satisfiable()) {
		puts("Yes");
		auto ans = t.answer();
		rep(i, n) cout << (ans[i] ? y[i] : x[i]) << endl;
	} else {
		puts("No");
	}
}

Measured memory_bytes: 3744
Sa = input()
Sb = input()
Sc = input()

a_i = 0
b_i = 0
c_i = 0

user = Sa[a_i]
a_i += 1
while True:
    if user == 'a':
        if a_i == len(Sa):
            print("A")
            exit()
        user = Sa[a_i]
        a_i += 1
    if user == 'b':
        if b_i == len(Sb):
            print("B")
            exit()
        user = Sb[b_i]
        b_i += 1
    if user == 'c':
        if c_i == len(Sc):
            print("C")
            exit()
        user = Sc[c_i]
        c_i += 1

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
int main() {
    int n;
    cin >> n;
    int y, m, d;
    while(n--) {
        cin >> y >> m >> d;
        int ans = 0;
        m--; d--;
        while(y != 1000 || m != 0 || d != 0) {
            ans++;
            d++;
            int last;
            if(y % 3 == 0) {
                last = 20;
            } else {
                last = (m % 2 == 0 ? 20 : 19);
            }
            if(last == d) {
                d = 0;
                m ++;
            } 
            if(m == 10) {
                y++;
                m = 0;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string alp = "abcdefghijklmnopqrstuvwxyz";
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}
void neg() {cout << - 1 << endl;}
void unhap() {cout << ":(" << endl;}

int main() {
  int h, w;
  cin >> h >> w;
  vector<string> grid(h);
  for (int i = 0; i < h; i++) cin >> grid.at(i);
  vector<vector<int>> cnt(h, vector<int>(w, 1));
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (grid.at(i).at(j) == '#') continue;
      int from = j;
      while (j < w && grid.at(i).at(j) == '.') j++;
      j--;
      for (int k = from; k <= j; k++) cnt.at(i).at(k) += j - from;
    }
  }
  for (int j = 0; j < w; j++) {
    for (int i = 0; i < h; i++) {
      if (grid.at(i).at(j) == '#') continue;
      int from = i;
      while (i < h && grid.at(i).at(j) == '.') i++;
      i--;
      for (int k = from; k <= i; k++) cnt.at(k).at(j) += i - from;
    }
  }
  int maxcnt = 0;
  for (int i = 0; i < h; i++)
    for (int j = 0; j < w; j++)
      maxcnt = max(maxcnt, cnt.at(i).at(j));
  cout << maxcnt << endl;
}

Measured memory_bytes: 20096
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main() {
	int n;
	cin>>n;
	vector <double> v(n+1);
	for(int i=1;i<=n;++i)cin>>v[i];
	vector <vector <double> > arr(n+1,vector <double> (n+1,0));
	for(int i=0;i<=n;++i)arr[0][i]=0;
	arr[1][0]=1.0-v[1];
	for(int i=2;i<=n;i++)arr[i][0]=arr[i-1][0]*(1.0-v[i]);
	arr[1][1]=v[1];
	for(int i=2;i<=n;i++)arr[i][i]=arr[i-1][i-1]*v[i];
	for(int i=1;i<=n;++i){
	    for(int j=1;j<i;++j){
	        arr[i][j]=arr[i-1][j]*(1.0-v[i])+arr[i-1][j-1]*v[i];
	    }
	}
	double ans=0;
	for(int i=1+n/2;i<=n;i++)ans+=arr[n][i];
	printf("%.10f",ans);
	return 0;
}


Measured memory_bytes: 70656
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define rep(i, a, n) for (int i=(a); i<(n); i++)
#define per(i, a, n) for (int i=(a); i>(n); i--)
typedef long long ll;
const int maxn = 2e5+5;
const int mod = 1e9+7;
using namespace std;


void slove() {
	ll h1,m1,h2,m2,k;
	cin >> h1 >> m1 >> h2 >> m2 >> k;
	ll d1 = h2-h1, d2 = m2-m1;
	if (d2 < 0) d1--, d2+=60;
	cout << d1*60 + d2 - k;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef DEBUG
	freopen("C:\\Users\\Fish_Brother\\Desktop\\in", "r", stdin);
	//freopen("C:\\Users\\Fish_Brother\\Desktop\\out", "w", stdout);
#endif
	//int t; cin >> t; while(t--)
	slove();

	return 0;
}

Measured memory_bytes: 3668
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front

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

#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
double pi = 3.141592653589793;
ll mod = 1000000007;
ll INF = 1000000001;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;



int main(){
	vi a(3);
	rep(i,3)
	cin>>a[i];
	sort(a.begin(),a.end());
	cout<<a[0]+a[1]<<endl;
    return 0;
}






Measured memory_bytes: 256
from collections import deque, Counter


class UnionFind:
    def __init__(self, v):
        self.v = v
        self._tree = list(range(v + 1))
        self._counter = Counter(self._tree)

    def _root(self, a):
        queue = deque()
        while self._tree[a] != a:
            queue.append(a)
            a = self._tree[a]
        while queue:
            index = queue.popleft()
            self._tree[index] = a
        return a

    def union(self, a, b):
        root_a = self._root(a)
        root_b = self._root(b)
        if root_a == root_b:
            return 0

        self._tree[root_b] = root_a
        ca = self._counter[root_a]
        cb = self._counter[root_b]
        self._counter[root_a] += cb
        self._counter[root_b] = 0
        return ca * cb

    def find(self, a, b):
        return self._root(a) == self._root(b)


N, M = map(int, input().split(' '))
edges = [tuple(map(int, input().split(' '))) for _ in range(M)]

score = N * (N - 1) // 2
union_find = UnionFind(N)
scores = []

for a, b in reversed(edges):
    scores.append(score)
    if score == 0:
        continue
    minus = union_find.union(a, b)
    score -= minus

for s in reversed(scores):
    print(s)


Measured memory_bytes: 32168
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
#include <cassert>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>

#define cauto const auto&
#define ALL(v) begin(v),end(v)
#else
#define ALL(v) (v).begin(),(v).end()
#endif

using namespace std;


namespace{
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
	v.assign(a, vector<T>(b, t));
}
template <class T> inline T &chmin(T &x, const T &y){ return x = min(x, y); }
template <class T> inline T &chmax(T &x, const T &y){ return x = max(x, y); }
template <class F, class T>
void convert(const F &f, T &t){
	stringstream ss;
	ss << f;
	ss >> t;
}


#define REP(i,n) for(int i=0;i<int(n);++i)
#define RALL(v) (v).rbegin(),(v).rend()


#define MOD 1000000007LL
#define EPS 1e-8

LL powmod(LL x, LL y){
	LL a = 1;
	while(y){
		if(y & 1){ a = a * x % MOD; }
		x = x * x % MOD;
		y >>= 1;
	}
	return a;
}

LL fact[210000];

LL comb(int n, int k){
	return fact[n] * powmod(fact[n - k] * fact[k] % MOD, MOD - 2) % MOD;
}

void mainmain(){
	fact[0] = 1;
	for(int i = 1; i < 210000; ++i){
		fact[i] = fact[i - 1] * i % MOD;
	}
	int n, m;
	cin >> n >> m;
	LL ans = 1;
	for(int i = 2; i * i <= m; ++i){
		if(m % i == 0){
			int c;
			for(c = 0; m % i == 0; ++c){ m /= i; }
			ans = ans * comb(c + n - 1, c) % MOD;
		}
	}
	if(m > 1){
		ans = ans * n % MOD;
	}
	cout << ans << endl;
}



}
int main() try{
//	ios::sync_with_stdio(false); cin.tie(0);
	cout << fixed << setprecision(10);
	cerr << fixed << setprecision(4);
	mainmain();
}
catch(...){}


Measured memory_bytes: 1920
#include <stdio.h>
const unsigned long long int MOD = 1000000007;
unsigned long long int A[300000];
int main()
{
    unsigned long long int N, res = 0, d = 1, c;
    scanf("%llu ", &N);
    for (int i = 0; i < N; ++i) scanf("%llu", A+i);
    for (int j = 0; j < 60; ++j) {
        c = 0;
        for (int i = 0; i < N; ++i) {
            if (A[i] & 1) c++;
            A[i] >>= 1;
        }
        res += (((c * (N - c)) % MOD) * d) % MOD;
        d *= 2;
        d %= MOD;
    }
    printf("%llu\n", res%MOD);
    return 0;
}


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

using namespace std;

using ll = long long;
using P = pair<int, int>;

const ll MOD = 1000000007;

ll modpow(ll x, ll n, ll mod = MOD) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

ll f[100005];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());

    vector<int> b(n);
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    sort(b.begin(), b.end());

    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        f[i] = f[i-1]*i%MOD;
    }

    ll ans = 1;
    for (int i = 0, j = 1; i < n; i++) {
        int L1 = min(a[i], b[i]);
        int R1 = max(a[i], b[i]);
        while (j < n) {
            int L2 = min(a[j], b[j]);
            int R2 = max(a[j], b[j]);
            if (R1 < L2) break;
            j++;
        }

        int num = max(j - i, 0);
        (ans *= num) %= MOD;
    }
    cout << ans << endl;
    return 0;
}

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

signed main(){
	int K;
	string S;
	cin >> K;
	cin >> S;
	if(S.length() <= K)
		cout << S << endl;
	else{
		for(int i = 0; i < K; i++)
			cout << S[i];
		cout << "..." << endl;
	}

	return 0;	
}

Measured memory_bytes: 3624
#include <stdio.h>
#include <iostream>
using namespace std;




int main() {
	int n,wt;
	int v[105];
	int w[105];
	int dp[100010];
	
	cin >> n >> wt;

	for (int i=0;i<n;i++) {
		cin >> v[i] >> w[i];
	}

	for (int i=0;i<n;i++) {
		for (int j=wt;j>=w[i];j--) {
			dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
		}
	}

	cout << dp[wt] <<endl;

	
	return 0;
}


Measured memory_bytes: 3124
#include<bits/stdc++.h>
using namespace std;
long long a[1100], b[1100], c[1100], sa[1100], sb[1100], sc[1100], memo[1000010], ans[3000010];

int main(void){
    int x, y, z, k;
    cin >> x >> y >> z >> k;
    for(int i=0;i<x;++i)cin >> a[i];
    for(int i=0;i<y;++i)cin >> b[i];
    for(int i=0;i<z;++i)cin >> c[i];
    sort(a, a+x, greater<long long>());
    sort(b, b+y, greater<long long>());
    sort(c, c+z, greater<long long>());
    int p = 0;
    for(int i=0;i<x;++i){
        for(int j=0;j<y;++j){
            memo[p] = a[i]+b[j];
            ++p;
        }
    }
    p=0;
    sort(memo, memo+(x*y), greater<long long>());
    for(int i=0;i<k;++i){
        for(int j=0;j<min(z,k);++j){
            ans[p] = memo[i] + c[j];
            ++p;
        }
    }
    sort(ans, ans+(k*min(z,k)), greater<long long>());
    for(int i=0;i<k;++i){
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 31616
/*input
7
994 518 941 851 647 2 581
*/
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#ifdef leowang
#define debug(...) do{\
	fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}
//}}}
const ll maxn=300005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}



int main()
{
	//IOS;
	int n;
	cin>>n;
	int ans=0;
	REP(i,n){
		int x;
		cin>>x;
		ans+=x-1;
	}
	cout<<ans<<'\n';

	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) long long((x).size())
#define OUT(x) cout << (x) << endl
typedef long long ll;

int main() {
    int a, b;
    cin >> a >> b;
    if ((a >= 1 && a <= 9) && (b >= 1 && b <= 9))
        OUT(a * b);
    else
        OUT(-1);
}


Measured memory_bytes: 256
N,M,X,Y = map(int, input().split())
x = [int(i) for i in input().split()]
y = [int(i) for i in input().split()]

for Z in range(max(x) + 1, min(y) + 1):
    if X < Z <= Y:
        print("No War")
        exit()

print("War")

Measured memory_bytes: 3060
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <random>



using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)















int main(){
    ll n;
    string s;
    cin >> n >> s;
    if(n % 2 == 1){
        cout << "No" << endl;
        return 0;
    }
    REP(i, n / 2){
        if(s[i] != s[n / 2 + i]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 384
#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>;

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

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

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

	map<char, int> mp;
	rep(i, s.size()){
		mp[s.at(i)]++;
	}

	if(mp.size() == 2 && mp[s.at(0)] == 2)
		cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef int64_t ll;
typedef long double ld;
const ll MOD=1000000007;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
long long gcd(long long a,long long b){
    ll gcdmax=max(a,b);
    ll gcdmin=min(a,b);
    while(true){
        if(gcdmax%gcdmin==0)break;
        else gcdmax%=gcdmin;
        swap(gcdmin,gcdmax);
    }
    return gcdmin;
}
ll powerup(ll N,ll P,ll M){
    if(P==0)return 1;
    else if(P%2==0){
        ll t=powerup(N,P/2,M);
        return t*t%M;
    }
    else return N*powerup(N,P-1,M)%M;
}
vector<ll> find_divisor(ll N){
  ll k=1;
  while(k*k<=N){
    k++;
  }
  vector<ll> A(1);
  rep(i,k){
    if(i==1)A.at(0)=1;
    else if(i>=2){
      if(N%i==0)A.push_back(i);
    }
  }
  ll t=0;
  t=A.size();
  rep(i,t){
    if(A.at(t-i-1)*A.at(t-i-1)!=N)A.push_back(N/A.at(t-1-i));
  }
  return A;
}

int main()
{
  ll N,K,d,b;
  cin>>N>>K;
  vector<ll> A(N);
  rep(i,N){
      cin>>d;
      rep(j,d){
          cin>>b;
          A.at(b-1)++;
      }
  }
  ll ans=0;
  rep(i,N){
      if(A.at(i)==0)ans++;
  }
  cout<<ans<<endl;
}

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

const int N=100005;
int n,m,a[N],b[N],f[N],dfn[N],cnt;
int v[N],nxt[N],head[N],dp[N],ans;
bool vis[N];

void bfs()
{
	queue<int> q;
	for(int i=1;i<=n;i++)
	{
		if(!f[i]) q.push(i),dfn[++cnt]=i;
	}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i>0;i=nxt[i])
		{
			f[v[i]]--;
			if(!f[v[i]]) q.push(v[i]),dfn[++cnt]=v[i];
		}
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d",&a[i],&b[i]);
	for(int i=1;i<=m;i++)
	{
		v[i]=b[i],f[v[i]]++;
		nxt[i]=head[a[i]],head[a[i]]=i;
	}
	bfs();
	memset(head,-1,sizeof(head));
	for(int i=1;i<=m;i++)
	{
		v[i]=a[i];
		nxt[i]=head[b[i]],head[b[i]]=i;
	}
	for(int i=1;i<=n;i++)
	{
		int x=dfn[i];
		for(int j=head[x];j>0;j=nxt[j])
		{
			dp[x]=max(dp[x],dp[v[j]]+1);
		}
		ans=max(ans,dp[x]);
	}
	printf("%d\n",ans);
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << ": " << x << '\n'

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

const long long INF = 3e18 + 12;
const int inf = 1e9;

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

  int a, b, c;
  cin >> a >> b >> c;

  vector<int> v(b);

  rep(i, b) {
    v[i] = (a * i) % b;
  }

  auto r = find(all(v), c);

  if (r != v.end()) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }

  return 0;
}

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

int N;
int a[100010];
int s;
int ans;
int flag;
int main(){
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>s;
        a[s]++;
    }
    for(int i=0;i<100010;i++){
        if(a[i]!=0){
	   ans++;
           if(a[i]%2==0)flag++;
        }
    }
    if(flag%2!=0)ans--;
    cout<<ans<<endl;
}

Measured memory_bytes: 640
#include<iostream>
#include<cassert>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<deque>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
typedef pair<int, int>P;
const int MOD = 1e9 + 7;
const int INF = 1e10;
const long double PI = (acos(-1));


signed main() {
	int N;
	cin >> N;
	int ans = 0;
	for (int i = 1; i * i <= N; i++) {
		if (N % i == 0) {
			int n = N / i;
			if (i < n - 1)ans += n - 1;
		}
	}
	cout << ans << endl;
}

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

using namespace std;

int main()
{
    string a;
    cin >> a;
    bool ans = true;
    int l = a.size();
    while (l--)
    {
        if (a[l] == 'i' && a[l-1] == 'h')
        {
            ans = true;
        }
        else
        {
            ans = false;
            cout << "No";
            return 0;
        }
        l--;
    }
    if (ans)
    {
        cout << "Yes";
    }
    else
    {
        cout << "No";
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#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()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
#ifdef DEBUG_ 
#include "../program_contest_library/memo/dump.hpp"
#else
#define dump(...)
#endif
const ll INF = 1LL<<30;

int main(void) {
    string s;
    cin >> s;
    const ll n = s.size();

    int rui = 0;
    vector<int> dp1(n), dp2(1LL<<26, INF);
    dp1[0] = dp2[0] = 0;
    REP(i, n) {
        rui ^= 1LL<<(s[i]-'a');
        int mi = dp2[rui];
        REP(j, 26) chmin(mi, dp2[rui^(1LL<<j)]);
        dp1[i] = mi + 1;
        chmin(dp2[rui], dp1[i]); 
    }
    cout << dp1[n-1] << endl;

    return 0;
}

Measured memory_bytes: 263572
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    for (int i=0; i<N; i++) {
        cin >> A.at(i);
    }
    sort(A.begin(), A.end());
    vector<int> cnt(N);
    for (int i=0; i<N; i++) {
        cnt.at(A.at(i) - 1)++;
    }
    int num = 0;
    for (int i=0; i<N; i++) {
        if (cnt.at(i) != 0) num++;
    }
    if (num <= K) cout << 0 << endl;
    else {
        sort(cnt.begin(), cnt.end(), greater<int>());
        int sum = 0;
        for (int i=0; i<K; i++) {
            sum += cnt.at(i);
        }
        int ans = N - sum;
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <unordered_map>
#include <string.h>
#include<iomanip>
#include <iterator>
#include <locale>

#define all(a) a.begin(),a.end()
#define VV(T) vector<vector< T > >
#define rep(i,N) for(int i = 0; i <N; i++)
#define repsg(i,s,g) for(int i = s; i <g; i++)
#define name(x) #x
using namespace std;

const int INF = INT_MAX;
const long long INFL =LONG_LONG_MAX;
const double PI = atan(1)*4;
const int MOD = pow(10,9)+7;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

typedef long long ll,LL;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pLL;


// vector入力
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x: vec) is >> x;
    return is;
}
// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){
    for(int i=0; i<vec.size(); i++){
        os << vec[i] << ( i+1 == vec.size() ? "" : " " );
    }
    return os;
}


int main() {
    int n,c,k;cin>>n>>c>>k;
    vint T(n);cin>>T;sort(all(T));
    
    // iにとって許容可能なのはTi ~ Ti+Kの間。
    
    // iの乗ったバスは、C人乗った or t = Ti+Kになった段階で出発。
    
    ll time = T[0]+k;
    ll cnt = 1;
    ll ans = 1;
    for(auto i = 1;i<n;i++){
        
        if(cnt == c || T[i]>time){ //満員 or 出発済み。
            cnt=1;
            ans++;
            time=T[i]+k;
            continue;
        }
        
        if(cnt<c && T[i]<=time) { //乗車可能。
            cnt++;
            continue;
        }
    }
    
    
    cout<<ans<<endl;
    
    return 0;
}








Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <iomanip>

typedef long long ll;

using namespace std;

int main(void)
{
    int a;
    cin >> a;

    vector<ll> data(a);

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

    sort(data.begin(), data.end(), greater<ll>());

    int flg = 0;

    for (int i = 0; i < a-1; i++) {
        if (data[i] == data[i+1]) {
            flg = 1;
            break;
        }
    }

    if (flg == 0) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }



    return 0;
}

Measured memory_bytes: 1792
from collections import defaultdict
from collections import deque
from collections import Counter
import itertools
import math

def readInt():
  return int(input())
def readInts():
  return list(map(int, input().split()))
def readChar():
  return input()
def readChars():
  return input().split()

a = readInt()
print(a+a**2+a**3)

Measured memory_bytes: 9392
#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

def dfs(node):
    tmp = data[node]
    for v in G[node]:
        if not visited[v]:
            visited[v]=1
            data[v]+=tmp
            dfs(v)
    return 0



n,q=map(int,input().split())
G=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    G[a].append(b)
    G[b].append(a)
data=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    data[p-1]+=x
visited=[0]*n
visited[0]=1
dfs(0)
print(*data)


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

int main() {
  vector<int> x(10);
  cin >> x.at(0) >> x.at(1) >> x.at(2)>> x.at(3) >> x.at(4);
  for (int i = 0; i < 5; i++) {
    if(x.at(i) == 0){
      cout << i+1 << endl;
      break;
    }
  }
}


Measured memory_bytes: 3568
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
//using System.Threading.Tasks;

namespace Print_a_Rectangle
{
    class Program
    {
        static void Main(string[] args)
        {
            String str;
            while ((str = Console.ReadLine()) != "0 0")
            {
                String[] ss = str.Split(' ');
                for (int i = 0; i < int.Parse(ss[0]); ++i)
                {
                    for (int j = 0; j < int.Parse(ss[1]); ++j)
                    {
                        Console.Write("#");
                    }
                    Console.WriteLine();
                }
                Console.WriteLine();
            }
        }
    }
}


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

typedef long long ll;
using namespace std;

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

	ll n;
	cin >> n;
    ll a[n];
    for(ll i = 0; i < n; i++) cin >> a[i];

    ll sum = 0;
    for(ll i = 0; i < n-1; i++) {
		for(ll j = i+1; j < n; j++) {
			sum += (a[i]*a[j]);
		}
    }
	cout << sum;
}


Measured memory_bytes: 256
def main():
    from collections import deque

    def traversal(ignore_idx):
        s = 0
        visited = [-1] * N
        visited[s] = 0

        dq = deque([s])
        while dq:
            v = dq.popleft()
            for u, edge_idx in g[v]:
                if ~visited[u] or edge_idx == ignore_idx:
                    continue
                dq.append(u)
                visited[u] = 0
        return all(~flg for flg in visited)  # 連結ならTrue

    N, M = map(int, input().split())
    g = tuple(set() for _ in range(N))
    for edge_idx in range(M):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add((b, edge_idx))
        g[b].add((a, edge_idx))

    ret = 0
    for ignore_idx in range(M):
        res = traversal(ignore_idx)
        if not res:
            ret += 1
    print(ret)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3316
#include <iostream>
#include <cstdio>

using namespace std;

string p[]={"AC","WA","TLE","RE"};

int n;
int d[5];
string str;

int main()
{
    cin>>n;
    while(n--)
    {
        cin>>str;
        for(int i=0;i<4;i++)
            if(str==p[i])
                d[i]++;
    }
    for(int i=0;i<4;i++)
        cout<<p[i]<<" x "<<d[i]<<endl;
    return 0;
}

Measured memory_bytes: 3608
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <iomanip>
#include <cmath>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define pie 3.141592653589793238462643383279
#define INF 1000000007
#define ggr getchar(); getchar();return 0;
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}

string s;
int ta, cnt1, cnt2;
bool mu = true;

signed main() {
	cin >> s;
	rep(i, s.size()) {
		if (s[i] != '9') {
			mu = false;
			break;
		}
	}
	rep(i, s.size()) {
		ta = ta * 10 + (s[i] - '0');
		cnt2 += (s[i] - '0');
	}
	while (ta >= 10) {
		ta /= 10;
		cnt1++;
	}
	if (mu) cout << (cnt1 + 1) * 9 << endl;
	else if (cnt2 <= (s[0] - '0' - 1) + cnt1 * 9)cout << (s[0] - '0' - 1) + cnt1 * 9 << endl;
	else cout << cnt2 << endl;
	ggr
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<int> a(100);
  for (int i=0;i<n;i++){
    cin >> a[i];
  }
  sort(a.begin(),a.end(),greater<int>());
  int count =1;
  for (int i=0;i<n-1;i++){
    if(a[i]!=a[i+1]){
      count++;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>
#include <iomanip>
#include <ctype.h>

using namespace std;
using ll = long long;

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

ll GCD(ll x, ll y) {
    if (y == 0) return x;
    else return GCD(y, x % y);
}

int main()
{
    int K, A, B;
    cin >> K;
    cin >> A >> B;

    int j=0;

    for(int i=A;i<=B;++i){
        if (i % K == 0) { ++j; }
    }

    if (j > 0) { cout << "OK" << endl; }
    else { cout << "NG" << endl; }

}


Measured memory_bytes: 3632
import java.util.*;
import java.awt.geom.Rectangle2D;

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

		while(sc.hasNextDouble()){
			double x1,y1,x2,y2;

			x1 = sc.nextDouble();
			y1 = sc.nextDouble();
			x2 = sc.nextDouble();
			y2 = sc.nextDouble();

			Rectangle2D r = new Rectangle2D.Double(x1,y1,x2-x1,y2-y1);
			double eps = 0.00000001;

			x1 = sc.nextDouble() - eps;
			y1 = sc.nextDouble() - eps;
			x2 = sc.nextDouble() + eps;
			y2 = sc.nextDouble() + eps;

			System.out.println(r.intersects(x1,y1,x2-x1,y2-y1) ? "YES" : "NO");
		}
	}
}

Measured memory_bytes: 12000
#include <iostream>

#include <algorithm>

#include <string>

#include <queue>

#include <vector>

using namespace std;
int main()
{
	int a[35][35] = {0};
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n;i++) {
		int k;
		cin >> k;
		for (int j = 1; j <= k; j++) {
			int b;
			cin >> b;
			a[0][b] ++;
		}

	}
	int ans=0;
	for (int i = 1; i <= m; i++) {
		if (a[0][i] == n)ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define MAX 2000001
#define VMAX 10000

int main(){
	unsigned short *A,*B;
	
	int C[VMAX+1];
	int n,i,j;
	scanf("%d",&n);
	
	A=malloc(sizeof(short)*n+1);
	B=malloc(sizeof(short)*n+1);
	
	for(i=0;i<=VMAX;i++)C[i]=0;
	
	for(i=0;i<n;i++){
		scanf("%hu",&A[i+1]);
		C[A[i+1]]++;
	}
	
	for(i=1;i<=VMAX;i++){
		C[i]=C[i]+C[i-1];
	}
	
	for(j=1;j<=n;j++){
		B[C[A[j]]]=A[j];
		C[A[j]]--;
	}
	
	for(i=1;i<=n;i++){
		if(i>1)printf(" ");
		printf("%d",B[i]);
	}
	printf("\n");
	
	return 0;
	
}

Measured memory_bytes: 9640
// atcoder dp_a
#include<iostream>
#include<cmath>
using namespace std; 
int main() {         	int n, i, j;    	cin >> n;    	int h[n];    	for(i=0;i<n;i++) {        	cin >> h[i];    	}         	int a[n];         	for(i=0;i<n;i++) {        	if(!i) a[i]=0;        	else if(i==1) a[i]=abs(h[0]-h[1]);        	else a[i]=min( a[i-1]+abs(h[i]-h[i-1]), a[i-2]+abs(h[i]-h[i-2]));    	}    	cout << a[n-1] << endl;    	return 0;
}

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

using namespace std;

int n, k;
int A[105];

int dp[100005];

bool solve(int c) {
  if (dp[c] != -1) {
    return dp[c];
  }
  for (int i = 0; i < n; i++) {
    if (c >= A[i] && !solve(c - A[i])) {
      return dp[c] = true;
    }
  }
  return dp[c] = false;
}

int main() {
  fill(dp, dp + 100005, -1);
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> A[i];
  }
  cout << (solve(k) ? "First\n" : "Second\n");
}


Measured memory_bytes: 3712
package main

import (
        "fmt"
        "os"
)

// https://atcoder.jp/contests/agc032/tasks/agc032_a
func main() {
        var N int
        fmt.Scan(&N)

        b := []int{}
        for i := 0; i < N; i++ {
                var tmp int
                fmt.Scan(&tmp)
                b = append(b, tmp)
        }

        // reverse
        br := []int{}
        for i := len(b) - 1; i >= 0; i-- {
                br = append(br, b[i])
        }

        a := make([]int, N)
        c := 0
        l := len(br)
        for i := 0; i < l; i++ {
                if l-i == br[i] {
                        a[N-1-c] = br[i]
                        c++

                        br = remove(br, i)
                        l = len(br)
                        if l == 0 {
                                break
                        }
                        i = -1
                }
        }
        if len(br) != 0 {
                fmt.Print("-1")
                os.Exit(0)
        }
        for i := 0; i < N; i++ {
                fmt.Println(a[i])
        }
}

func remove(arr []int, index int) []int {
        l := len(arr)
        res := []int{}
        for i := 0; i < l; i++ {
                if i == index {
                        continue
                }
                res = append(res, arr[i])
        }
        return res
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <stack>
#include <algorithm>
#include <cstdio>

using namespace std;

int main(){
	int n;
	string mes;
	stack<pair<int, int> > pos;
	while(cin >> n && n != 0){
		cin >> mes;
		for(int i = 0; i < n; i++){
			pair<int, int> tmp;
			cin >> tmp.first >> tmp.second;
			pos.push(tmp);
		}

		while(!pos.empty()){
			pair<int, int> tmp = pos.top();
			pos.pop();
			int sub = tmp.second-tmp.first;
			for(int i = 0; i < sub; i++){
				mes[tmp.first-1] = mes[tmp.first-1]+1>122?'a'+(mes[tmp.first-1]+1-123):mes[tmp.first-1]+1;
				mes[tmp.second-1] = mes[tmp.second-1]+1>122?'a'+(mes[tmp.second-1]+1-123):mes[tmp.second-1]+1;
			}
			
			char a = mes[tmp.first-1];
			mes[tmp.first-1] = mes[tmp.second-1];
			mes[tmp.second-1] = a;
		}
		cout << mes << endl;
	}
	return 0;
}

Measured memory_bytes: 1204
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;


#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++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; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }



typedef pair<long long, long long> Par;
typedef pair<int, Par> Edge;
vector<vector<Edge> > G;

int N, M, s, g;

inline long long func(long long t, long long a, long long b) {
    return t + (b + t+a-1) / (t+a);
}
inline long long calc(long long K, long long a, long long b) {
    long long sb = (long long)(sqrt(b));
    long long start = max(0LL, sb - a - 2);
    long long res = func(K, a, b);
    for (long long t = start; t < start + 5; ++t) {
        if (t < K) continue;
        res = min(res, func(t, a, b));
    }
    return res;
}

int main() {
    cin >> N >> M >> s >> g;
    --s, --g;
    G.clear(); G.resize(N);
    for (int i = 0; i < M; ++i) {
        int u, v; cin >> u >> v; --u, --v;
        long long a, b; cin >> a >> b;
        G[u].push_back(Edge(v, Par(a, b)));
        G[v].push_back(Edge(u, Par(a, b)));
    }
    
    const long long INF = 1LL<<60;
    vector<long long> dp(N, INF);
    priority_queue<pair<long long,int>, vector<pair<long long,int> >, greater<pair<long long,int> > > que;
    que.push(make_pair(0, s));
    dp[s] = 0;
    while (!que.empty()) {
        auto cur = que.top(); que.pop();
        int v = cur.second;
        long long t = cur.first;
        if (dp[v] < t) continue;
        
        //cout << v << ": " << dp[v] << endl;
        
        for (auto e : G[v]) {
            int to = e.first;
            long long a = e.second.first;
            long long b = e.second.second;
            long long dist = calc(t, a, b);
            if (chmin(dp[to], dist)) que.push(make_pair(dist, to));
        }
    }
    if (dp[g] < INF) cout << dp[g] << endl;
    else cout << -1 << endl;
}


Measured memory_bytes: 26532
#include<math.h>
#include<stdio.h>
int main(void)
{
	double x1, y1, x2, y2;
	double answer;
	scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
	answer = (x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1);
	printf("%f", sqrt(answer));
	return 0;
}


Measured memory_bytes: 2036
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int maxn = 1e5 + 5;
int main()
{
	int n , a[maxn ] , dp[maxn];
	scanf("%d",&n);
	for(int i = 1;i <= n;i++)scanf("%d",&a[i]);
	dp[1] = 0,dp[2] = fabs(a[1] - a[2]),dp[3] = fabs(a[1] - a[3]);
	for(int i = 1;i <= n;i++){
		if(dp[i + 1] + fabs(a[i+2] - a[i + 1]) > dp[i] + fabs(a[i]-a[i + 2]))dp[i + 2] = dp[i] + fabs(a[i] - a[i + 2]);
		else dp[i + 2] = dp[i + 1] + fabs(a[i + 2] - a[i +1]);
	}
	printf("%d\n",dp[n]);
	return 0;
}

Measured memory_bytes: 1024
//EDPC-Z
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using ll = long long;
using P = pair<int, int>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e18;
constexpr long long MOD = 1e9 + 7;

/*
    追加クエリの傾き a が単調の場合しか使えない (単調でない場合はLi Chao Treeを使う)
*/
template <typename T, bool isMin>
struct CHT {
#define F first
#define S second
    using P = pair<T, T>;
    deque<P> H;

    bool empty() const {
        return H.empty();
    }

    void clear() {
        H.clear();
    }

    inline int sgn(T x) {
        return x == 0 ? 0 : (x < 0 ? -1 : 1);
    }

    inline bool check(const P& a, const P& b, const P& c) {
        if (b.S == a.S || c.S == b.S)
            return sgn(b.F - a.F) * sgn(c.S - b.S) >=
                   sgn(c.F - b.F) * sgn(b.S - a.S);
        return (long double)(b.F - a.F) * sgn(c.S - b.S) /
                   (long double)(abs(b.S - a.S)) >=
               (long double)(c.F - b.F) * sgn(b.S - a.S) /
                   (long double)(abs(c.S - b.S));
    }

    void add(T a, T b) {
        if (!isMin) a *= -1, b *= -1;
        P line(a, b);
        if (empty()) {
            H.emplace_front(line);
            return;
        }
        if (H.front().F <= a) {
            if (H.front().F == a) {
                if (H.front().S <= b) return;
                H.pop_front();
            }
            while (H.size() > 1 && check(line, H.front(), H[1])) H.pop_front();
            H.emplace_front(line);
        } else {
            assert(a <= H.back().F);
            if (H.back().F == a) {
                if (H.back().S <= b) return;
                H.pop_back();
            }
            while (H.size() > 1 && check(H[H.size() - 2], H.back(), line))
                H.pop_back();
            H.emplace_back(line);
        }
    }

    inline T getY(const P& a, const T& x) {
        return a.F * x + a.S;
    }

    T query(T x) {
        assert(!empty());
        int l = -1, r = H.size() - 1;
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (getY(H[m], x) >= getY(H[m + 1], x))
                l = m;
            else
                r = m;
        }
        if (isMin) return getY(H[r], x);
        return -getY(H[r], x);
    }
};

signed main() {
    int n;
    ll c;
    cin >> n >> c;
    ll h[n];
    rep(i, n) {
        cin >> h[i];
    }
    CHT<ll, true> cht;
    ll dp[n];
    dp[0] = 0;
    rep(i, n) {
        if(i) dp[i] = cht.query(h[i]) + h[i] * h[i];
        cht.add(-2 * h[i], h[i] * h[i] + dp[i] + c);
    }
    cout << dp[n - 1] << endl;
    return 0;
}

Measured memory_bytes: 6656
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N = getN()
time = (N + 1000 - 1) // 1000
ans = time * 1000 - N
print(ans)

Measured memory_bytes: 78012
// D - No Need
#include <bits/stdc++.h>
using namespace std;

int main(){
	int N,K; cin>>N>>K;

	vector<int> A(N);
	for(int i=0; i<N; ++i) cin>>A[i];
	sort(A.begin(), A.end());

	int ans = N;
	int sum = 0;
	for(int i=N-1; i>=0; --i){
		if(sum+A[i]<K) sum += A[i];
		else ans = min(ans, i);
	}
	cout<< ans <<endl;
}

Measured memory_bytes: 384
mulMod a b = (a * b) `rem` (10^9+7)

prod 1 = 1
prod n = mulMod n (prod (n-1))

solve n m
    | (abs $ n - m) > 1 = 0
    | (abs $ n - m) == 1 = mulMod (prod n) (prod m)
    | otherwise = mulMod 2 (mulMod (prod n) (prod m))

main = do
    [n,m] <- map read . words <$> getLine :: IO [Int]
    print $ solve n m

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

int main() {
  int N;
  cin >> N;
  int a = N % 10;
  int b = N % 100  / 10;
  int c = N % 1000 / 100;
  int d = N / 1000;
  if ((a == b && b == c) || (b == c && c == d)) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.TreeMap;

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

    Map<String,Integer> map = new TreeMap<>();
    for(int i = 0;i < N;i++){
      String str = scan.next();
      if(map.containsKey(str)){
      map.put(str,map.get(str) + 1);
      }else{
        map.put(str,0);
      }
    }
    int maxv = 0;
    for(int v : map.values()){
      if(v > maxv) maxv = v;
    }
    for(String str : map.keySet()){
      if(map.get(str) == maxv){
        System.out.println(str);
      }
    }
  }
}

Measured memory_bytes: 77904
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define INF 9223372036854775807
#define MAX_ABQ 100000

typedef long long llong;
using namespace std;

llong a, b, q;
llong s[MAX_ABQ];
llong t[MAX_ABQ];
llong x[MAX_ABQ];

llong min(llong l, llong r) {
    return l < r ? l : r;
}

void get_closest(llong x, llong *left, llong *right, llong *set, llong length) {
    if(set[0] > x)
        *left = INF, *right = set[0];
    else if(set[length - 1] < x)
        *left = set[length - 1], *right = INF;
    else {
        llong *ptr_lower = lower_bound(set, set + length, x);
        llong *ptr_upper = upper_bound(set, set + length, x);
        *left = *(--ptr_upper);
        *right = *ptr_lower;
    }
}

llong solve(llong x) {
    llong x_l, dist_l = 0;
    llong x_r, dist_r = 0;
    llong flag_l[2] = {0, 0};
    llong flag_r[2] = {0, 0};

    llong l_shrine, r_shrine, l_temple, r_temple;

    get_closest(x, &l_shrine, &r_shrine, s, a);
    get_closest(x, &l_temple, &r_temple, t, b);

    //左側の地点を決定
    if(abs(x - l_shrine) < abs(x - l_temple)) {
        x_l = l_shrine;
        dist_l += abs(x - l_shrine);
        flag_l[0] = 1;
    } else {
        x_l = l_temple;
        dist_l += abs(x - l_temple);
        flag_l[1] = 1;
    }

    //右側の地点を決定
    if(abs(x - r_shrine) < abs(x - r_temple)) {
        x_r = r_shrine;
        dist_r += abs(x - r_shrine);
        flag_r[0] = 1;
    } else {
        x_r = r_temple;
        dist_r += abs(x - r_temple);
        flag_r[1] = 1;
    }

    llong next_x_ll, next_x_lr;
    //左側
    if(flag_l[0])
        get_closest(x_l, &next_x_ll, &next_x_lr, t, b);
    else
        get_closest(x_l, &next_x_ll, &next_x_lr, s, a);
    dist_l += min(abs(x_l - next_x_ll), abs(x_l - next_x_lr));

    
    llong next_x_rl, next_x_rr;
    //右側
    if(flag_r[0])
        get_closest(x_r, &next_x_rl, &next_x_rr, t, b);
    else
        get_closest(x_r, &next_x_rl, &next_x_rr, s, a);
    dist_r += min(abs(x_r - next_x_rl), abs(x_r - next_x_rr));

    return min(dist_l, dist_r);
}

int main(int argc, char **argv) {
    scanf("%d %d %d", &a, &b, &q);
    for(int i = 0; i < a; ++i)
        scanf("%lld", s + i);
    for(int i = 0; i < b; ++i)
        scanf("%lld", t + i);

    for(int i = 0; i < q; ++i) {
        llong x;
        scanf("%lld", &x);
        printf("%lld\n", solve(x));
    }

}

Measured memory_bytes: 2816
n,m = map(int, input().split())
Li = [[] for y in range(n)]
Li2 = []
a = 0
for x in range(n):
    Li[x] += list(map(int, input().split()))
for x in range(m):
    Li2.append(int(input()))
for x in range(n):
    for y in range(m):
        a += Li[x][y]*Li2[y]
    print(a)
    a = 0




Measured memory_bytes: 6024