akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)
#define pcnt __builtin_popcountll
#define rng(a) a.begin(), a.end()
#define sz(x) (int)(x).size()
#define v(T) vector<T>
#define vv(T) v(v(T))
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;

template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
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; }

struct UnionFind {
    vector<int> par;
    vector<int> rank;
    
    UnionFind(int n = 1) {
        init(n);
    }
    
    void init(int n = 1) {
        par.resize(n); rank.resize(n);
        for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0;
    }
    
    int root(int x) {
        if (par[x] == x) {
            return x;
        }
        else {
            int r = root(par[x]);
            return par[x] = r;
        }
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        return true;
    }
};

ll INF = 1001001001;
ll LINF = 1001001001001001001ll;

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

    UnionFind ds(13);
    ds.merge(1, 3);
    ds.merge(1, 5);
    ds.merge(1, 7);
    ds.merge(1, 8);
    ds.merge(1, 10);
    ds.merge(1, 12);
    ds.merge(4, 6);
    ds.merge(4, 9);
    ds.merge(4, 11);
    int x, y;
    cin>>x>>y;
    if (ds.issame(x, y)) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

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

int main() {
  string S;
  cin >> S;
    
  int len = S.size();
  bool flg = true;
  
  string s1 = S.substr(0, (len - 1) / 2);
  string s2 = S.substr((len + 3) / 2 - 1, (len - 1) / 2);
    
  for (int i = 0; i < s1.size(); i++) {
    if (s1[i] != s1[s1.size() - 1 - i]) flg = false;  
  }
  for (int i = 0; i < s2.size(); i++) {
    if (s2[i] != s1[s2.size() - 1 - i]) flg = false;
  }
  
  string res = flg ? "Yes" : "No";
  cout << res << endl;
  
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
class Main {
	public static void main(String[] args){
		try(Scanner sc = new Scanner(System.in)){
			int N = Integer.parseInt(sc.next());
			Card[] p=new Card[N];
			Card[] q=new Card[N];
			Card[] r=new Card[N];
			
			for(int i=0;i<N;i++) {
				String s=new String(sc.next());
				p[i] = new Card(s);
				q[i] = new Card(s);
				r[i] = new Card(s);
			}
			
			//Bubble sort
			for(int i=0;i<N;i++){
				for(int j=N-1;j>i;j--){
					if(q[j].compareTo(q[j-1])<0){
						Card tmp=q[j];
						q[j]=q[j-1];
						q[j-1]=tmp;
					}
				}
			}
			
			//Colleciton sort
			for(int i=0;i<N;i++){
				int minj=i;
				for(int j=i;j<N;j++){
					if(r[j].compareTo(r[minj])<0){
						minj=j;
					}
				}
				Card tmp=r[i];
				r[i]=r[minj];
				r[minj]=tmp;
			}
			
			boolean BC=isStable(p,q);
			boolean SC=isStable(p,r);
			
			
			
			System.out.print(q[0]);
			for(int i=1;i<N;i++)System.out.print(" "+q[i]);
			System.out.println();
			System.out.println(BC?"Stable":"Not stable");
			System.out.print(r[0]);
			for(int i=1;i<N;i++)System.out.print(" "+r[i]);
			System.out.println();
			System.out.println(SC?"Stable":"Not stable");
		}
	}
	
	
	public static boolean isStable(Card[] c1, Card[] c2){
		final int kind=13;
		boolean isStable=true;
		int N=c1.length;
		StringBuilder[] suit1 =new StringBuilder[kind];
		StringBuilder[] suit2 =new StringBuilder[kind];
		for(int i=0;i<kind;i++){
			suit1[i]= new StringBuilder();
			suit2[i]= new StringBuilder();
		}
		for(int i=0;i<N;i++){
			suit1[c1[i].n-1].append(c1[i].toString());
			suit2[c2[i].n-1].append(c2[i].toString());
		}
		for(int i=0;i<kind;i++){
			if(!suit1[i].toString().isEmpty()){
				isStable=isStable&&(suit1[i].toString().equals(suit2[i].toString()));
			}
		}
		return isStable;
	}
}



class Card implements Comparable<Card>{
	String s;
	int n;
	public String toString(){
		return s;
	}
	Card(String s){
		this.s=s;
		this.n=Integer.parseInt(s.substring(1));
	}
	public int getNumber(){
		return this.n;
	}
	public int compareTo(Card c){
		return this.n-c.n;
	}
	
}

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

using namespace std;

long long inf=1000000007;

int main(){
	for(int i=1;i<=5;i++){
		int a;
		cin>>a;

		if(a==0){
			cout<<i<<endl;
			return 0;
		}
	}

	return 0;
}


Measured memory_bytes: 3616
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <deque>
#define INF_INT (INT_MAX / 2)
#define INF_LONG (LONG_MAX / 2)
//#define DEBUG true
#define DEBUG false
using namespace std;

const int MAX = 100001;
const int MOD = 1000000007;

typedef long long ll;
typedef pair< int, int > pii;
typedef pair< ll, ll > pll;
typedef pair< ll, int > pli;
typedef pair< int, ll > pil;

ll pow(ll a, int b){
  ll r = 1;
  for(int i = 0; i < b; i++){
    r *= a;
  }
  return r;
}

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

  int n, m;
  cin >> n >> m;
  int p[m], y[m];
  for(int i = 0; i < m; i++) cin >> p[i] >> y[i];

  vector< set< pii > > v(n);
  for(int i = 0; i < m; i++){
    v[p[i] - 1].insert(make_pair(y[i], i));
  }

  ll id[m];
  for(int i = 0; i < n; i++){
    int x = 0;
    for(pii pi: v[i]){
      int j = pi.second;
      id[j] = p[j] * pow(10, 6) + (x + 1);
      ++x;
    }
  }

  char buf[20 * m];
  for(int i = 0; i < m; i++){
    sprintf(buf + (13 * i), "%012lld\n", id[i]);
  }

  cout << buf;

  return 0;
}


Measured memory_bytes: 11392
fun main() {
    val (a, v) = readLine()!!.split(" ").map(String::toLong)
    val (b, w) = readLine()!!.split(" ").map(String::toLong)
    val t = readLine()!!.toLong()
    if (a == b) {
        println("YES")
        return
    }
    val vec = if (a < b) 1 else -1
    val at = a + v * t * vec
    val bt = b + w * t * vec

    println(
        if (at == bt || a < b && at > bt || a > b && at < bt) {
            "YES"
        } else {
            "NO"
        }
    )
}


Measured memory_bytes: 36392
H, W = map(int, input().split())

a = ["" for i in range(H)]
for i in range(H):
    a[i] = input()

row_deleted = [False for i in range(H)]
col_deleted = [False for i in range(W)]

for i in range(H):
    all_white = True
    for e in a[i]:
        if e != ".":
            all_white = False
    
    if all_white:
        row_deleted[i] = True
    
for i in range(W):
    all_white = True
    for j in range(H):
        if not row_deleted[j] and a[j][i] != ".":
            all_white = False
    
    if all_white:
        col_deleted[i] = True
        
for i in range(H):
    if row_deleted[i]:
        continue
    for j in range(W):
        if col_deleted[j]:
            continue
        print(a[i][j], end = '')
    print("")

Measured memory_bytes: 4468
import sys

input = sys.stdin.readline
H, N = map(int, input().split())
magic = [list(map(int, input().split())) for _ in range(N)]

max_damage = max(damage for damage, cost in magic)
dp = [0] * (H + max_damage)

for i in range(1, H + max_damage):
    dp[i] = min(dp[i - damage] + cost for damage, cost in magic)

ans = min(dp[H:])

print(ans)


Measured memory_bytes: 3668
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll MOD = 1000000007;
ll INFL = 1ll << 60;
ll INF = 1 << 30;
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[8] = {1, 1, 0, -1, -1, -1, 0, 1};

int main() {
  ll a, b, k;
  cin >> a >> b >> k;
  for (int i = a; i <= b; i++) {
    if (abs(a - i) < k || abs(b - i) < k)
      cout << i << endl;
  }
}


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

using namespace std;


int main() {
    int N;
    cin >> N;
    switch(N) {
        case 1:
            cout << "Hello World" << endl;
            break;
        case 2:
            int a, b;
            cin >> a >> b;
            cout << a + b << endl;
            break;
    }
    return 0;
}

Measured memory_bytes: 256
// We only fail when we stop trying
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define endl '\n'
#define D(x) cerr << #x << " = " << (x) << '\n'
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

const int N = 3007;

int n;
int arr[N];
long long dp[N][N];

int main()
{
  cin >> n;
  for(int i = 0 ; i < n ; i++)
    cin >> arr[i];
  for(int i = 0 ; i < n ; i++)
    dp[i][i] = arr[i];
  for(int len = 2; len <= n; len++) {
    for(int i = 0; i + len <= n; i++) {
      int j = i + len - 1;
      dp[i][j] = max(arr[i] - dp[i + 1][j], arr[j] - dp[i][j - 1]);
    }
  }
  cout << dp[0][n - 1] << endl;
  return 0;
}


Measured memory_bytes: 70016
def cmb(n,r,mod):
    if r<0 or r>n:return 0
    r=min(r,n-r)
    return g1[n]*g2[r]*g2[n-r]%mod


mod=998244353
n,m,k=map(int,input().split())

g1=[1,1]
g2=[1,1]
inverse=[0,1]

for i in range(2,n):
    g1.append((g1[-1]*i)%mod)
    inverse.append((-inverse[mod%i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1]%mod))

ans=(m*(m-1)**(n-1))%mod
for i in range(1,k+1):
    ans +=cmb(n-1,i,mod)*m*pow(m-1,n-1-i,mod)
    ans %=mod
print(ans)

Measured memory_bytes: 117936
#include <bits/stdc++.h>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD ((ll)(1e9+7))
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
template<class T> inline bool chmin(T& a, T b){return a>b ? a=b, true : false;}
template<class T> inline bool chmax(T& a, T b){return a<b ? a=b, true : false;}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

int main(void)
{
    int N;
    cin >> N;
    vector<int> P(N);
    for (int i = 0; i < N; i++) {
        cin >> P[i];
    }
    vector<int> Q(N);
    for (int i = 0; i < N; i++) {
        cin >> Q[i];
    }
    vector<int> A(N);
    iota(ALL(A),1);

    int a = 0, b = 0;
    int c = 1;
    do {
        bool flag = true;
        if(a == 0) REP(i, N){
            if(P[i] != A[i]) {
                flag = false;
                break;
            }
        }
        if(a == 0 && flag) a = c;

        flag = true;
        if(b == 0) REP(i, N){
            if(Q[i] != A[i]) {
                flag = false;
                break;
            }
        }
        if(b == 0 && flag) b = c;
        c++;

        if(a != 0 && b != 0) break;
    } while (next_permutation(A.begin(), A.end()));

    pr(abs(a-b));
}

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

public class Main {
    public static void main(String[] args) {
        try {
            // 標準入力
            InputStreamReader isr = new InputStreamReader(System.in);
            BufferedReader br = new BufferedReader(isr);
            String s = br.readLine();
            String ans = "";
            for (int i = 0; i < s.length(); i++) {
                String tmp = s.substring(i, i + 1);
                if ("B".equals(tmp)) {
                    if (ans.length() > 0) {
                        ans = ans.substring(0, ans.length() - 1);
                    }
                } else {
                    ans = ans + tmp;
                }
            }
            System.out.println(ans);
        } catch (IOException e) {
            e.printStackTrace();
           }
    }
}


Measured memory_bytes: 21076
def f(n):
    return n*(n+1)//2

import re
S=input()
T = re.findall('<+|>+', S)
N=[len(i) for i in T]
sum_=0
A=[]
B=[]
if '<' in T[0]:
    A.append(0)
    B.append(len(T[0]))
    #print(0,len(T[0]))
for i,s in enumerate(T):
    if '>' in s:
        if i+1 < len(T):
            #print(len(T[i]),len(T[i+1]))
            A.append(len(T[i]))
            B.append(len(T[i+1]))
if '>' in T[-1]:
    #print(len(T[-1]),0)
    A.append(len(T[-1]))
    B.append(0)
sum_=0
for i in range(len(A)-1):
    if B[i] < A[i+1]:
        sum_ += f(A[i+1])
        sum_ += f(B[i]-1)
    else:
        sum_ += f(B[i])
        sum_ += f(A[i+1]-1)
sum_ += f(A[0])
sum_ += f(B[-1])
print(sum_)

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;



int h1,m1,h2,m2,k;

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

    cin>>h1>>m1>>h2>>m2>>k;

    int t1 = h1*60 + m1;
    int t2 = h2*60 + m2;

    cout<<(t2-t1-k)<<endl;
    
    return 0;
}


Measured memory_bytes: 3640
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <map>

int main()
{
	int n, w;
	std::cin >> n >> w;
	std::vector<std::pair<int, int>> vec;
	vec.reserve(n);
	for (int i = 0; i < n; ++i)
	{
		std::pair<int, int> p;
		std::cin >> p.second >> p.first;
		vec.push_back(p);
	}
	std::map<int, int> mp;
	mp[0] = 0;
	std::vector<std::pair<int, int>> temp;
	temp.reserve(100005);
	for (int i = 0; i < n; ++i)
	{
		for (std::pair<int, int> p : mp)
			temp.push_back(p);
		std::pair<int, int> var = vec[i];
		for (std::pair<int, int> p : temp)
		{
			if (p.second + var.second <= w)
			{
				int& weight = mp[p.first + var.first];
				if (weight == 0)
					weight = p.second + var.second;
				else if (p.second + var.second <= w)
					weight = std::min(weight, p.second + var.second);
			}
		}
		temp.clear();
	}
	std::cout << mp.rbegin()->first << '\n';
	return 0;
}

Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N;
    cin >> N;
    bool b = false;
    for (int i = 0; i < N; i++) {
        string C;
        cin >> C;
        if (C == "Y") {
            b = true;
            break;
        }
    }
    if (b) {
        cout << "Four" << endl;
    } else {
        cout << "Three" << endl;
    }
}

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

int main(){
  int N,K;cin>>N>>K;
  map<int, vll> sushi_list;

  for (int i=0;i<N;++i){
    int t;cin>>t;ll d;cin>>d;
    sushi_list[t].push_back(d);
  }

  vll winner, loser;

  for (auto p: sushi_list){
    vll q=p.second;
    sort(q.begin(), q.end(), greater<ll>());

    int M=q.size();
    winner.push_back(q[0]);
    if(M>1){
      for (int i=1;i<M;++i) loser.push_back(q[i]);
    }
  }

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

  int W=winner.size(), L=loser.size();

  vll w_cum(W+1), l_cum(L+1);w_cum[0]=0, l_cum[0]=0;
  for (int i=0;i<W;++i){w_cum[i+1]=w_cum[i]+winner[i];}
  for (int i=0;i<L;++i){l_cum[i+1]=l_cum[i]+loser[i];}

  ll ans=0;
  int K_=min(K, W);
  for (int x=1;x<=K_;++x){
    if(K-x<=L){
      ll tmp=(ll)x*x+w_cum[x]+l_cum[K-x];
      ans=max(ans, tmp);
    }
  }
  cout << ans << endl;
  return 0;
}


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

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<ll, ll> P;

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

struct PairCompare {
	inline bool operator() (const P& a1, const P& a2)
	{
		if (a1.first == a2.first)	return a1.second < a2.second;
		return a1.first < a2.first;
	}
};

int main(void)
{
	ll n, k;
	cin >> n >> k;
	vector<ll> as(n);
	rep(i, n) cin >> as[i];
	vector<ll> bs(n, 0);
	vector<ll> cs(n, 0);
	rep(i, n) {
		rep(j, n) {
			if (j > i) {
				if (as[i] > as[j]) {
					bs[i]++;
				}
			}
			if (as[i] > as[j]) {
				cs[i]++;
			}
		}
	}
	ll sum = 0;
	const ll mod = (ll)1e9 + 7;
	auto km = k % mod;
	auto kmp = (k-1) % mod;
	rep(i, n) {
		sum += bs[i] * (k % mod);
		sum %= mod;
		sum += cs[i] * ((k*(k-1) - k*(k-1)/2)%mod);
		sum %= mod;
	}
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep0(i,n) for (int i = 0; i < (n); ++i)  //0index
#define rep1(i,n) for (int i = 1; i < (n); ++i)  //1index
#define REP(i,a,b) for (int i = a; i < (b); ++i)  //aからb - 1まで
#define mREP(i,a,b) for (int i = a; i > (b); --i)  //逆
#define all(x) (x).begin(),(x).end()
const int INF = 1000000007;  //最大値兼MOD
typedef long long ll;
using namespace std;

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; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }  //GCD

bool is_prime(long long n) {  //素数判定
  for(int64_t i = 2; i * i <= n; i++) {
    if(n % i == 0) return false;
  }
  return true;
}

int main(){
  int n,m;
  cin >> n >> m;
  vector<int>v(50);
  rep0(i,n){
    int k;
    cin >> k;
    rep0(j,k){
      int temp;
      cin >> temp;
      v[temp]++;
    }
  }
  int ans = 0;
  rep1(l,m+1){
    if(v[l] == n){
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <complex>
#include <cstdio>

using namespace std;

typedef complex<double> P;

struct Edge {
	int to;
	double cost;
};
bool operator <(const Edge& n1, const Edge& n2) {
	return n1.cost < n2.cost;
}
bool operator >(const Edge& n1, const Edge& n2) {
	return n2 < n1;
}

int main() {
	int N, M; cin >> N >> M;
	vector<P> piles(N);
	for (int i = 0; i < N; ++i) {
		int x, y; cin >> x >> y;
		piles[i] = P(x, y);
	}

	vector< vector<Edge> > edges(N);
	for (int i = 0; i < M; ++i) {
		int p, q; cin >> p >> q; --p, --q;
		double c = abs(piles[p]-piles[q]);
		edges[p].push_back( (Edge){q, c} );
		edges[q].push_back( (Edge){p, c} );
	}

	double ans = 0;
	vector<bool> isMerged(N, false);
	for (int i = 0; i < N; ++i) {
		priority_queue<Edge> Q; Q.push( (Edge){i, 0} );
		while ( !Q.empty() ) {
			Edge edge = Q.top(); Q.pop();
			int n = edge.to;
			double cost = edge.cost;

			if (isMerged[n]) continue;
			isMerged[n] = true;
			ans += cost;

			for (int i = 0; i < edges[n].size(); ++i) {
				Q.push(edges[n][i]);
			}
		}
	}

	double sum = 0;
	for (int i = 0; i < edges.size(); ++i) {
		for (int j = 0; j < edges[i].size(); ++j) {
			sum += edges[i][j].cost;
		}
	}
	ans = sum/2 - ans;

	printf("%.10f\n", ans);
}

Measured memory_bytes: 3588
{-# OPTIONS_GHC -Wall -Werror #-}

import Control.Applicative

qq :: Int -> Int -> String
qq x y = show x ++ "x" ++ show y ++ "=" ++ show (x * y)

main :: IO ()
main = mapM_ putStrLn $ qq <$> [1..9] <*> [1..9]

Measured memory_bytes: 3572
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;

int main()
{
    int N;
    cin >> N;
    vector<int> cost(N);
    for(int i = 0 ; i < N ; i++)
       cin >> cost[i];
    
    vector<int> dp(N+1);
    dp[0] = 0; dp[1] = abs(cost[1] - cost[0]);
    for(int i = 2 ; i < N ; i++)
    {
        dp[i] = min(dp[i-1] + abs(cost[i] - cost[i-1]) , dp[i-2] + abs(cost[i] - cost[i-2]) );
    }

    cout << dp[N-1];

}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
#include <stdio.h>
 
using namespace std;
 
#define int long long
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(i, a) for (auto &i: (a))
#define sz(x) (int)(x).size()
#define all(v) (v).begin(), (v).end()
#define fr(i, a, b) for (int i = (a); i <= (b); ++i)

void solve();

signed main () {
    clock_t beg = clock();
    cout << fixed << setprecision(15);
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    #endif 
    int t = 1; 
    // cin >> t;    
    int tt = t;
    while (t--) {
        // cout << "Case #" << tt - t << ": "; 
        solve();
    }
    cerr << "\nExecution time: " << (clock() - beg) / 1000 << '\n';
    return 0;
}
int n;
void solve() {  
    cin >> n;
    if (n % 1000 == 0)
        cout << 0;
    else
        cout << (1000 - n % 1000);
}          

Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define P pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007;
//最大公約数
int gcd(int s,int b){
    if(b==0)return s;
    return gcd(b,s%b);
}
signed main(){
   int r;
   cin>>r;
   cout<<r*r*3<<endl;
}


Measured memory_bytes: 256
using System;

namespace ABC117_D___XXOR
{
    class Program
    {
        static void Main(string[] args)
        {
            var NK = Array.ConvertAll(Console.ReadLine().Split(' '), long.Parse);
            var N = (int)NK[0]; var K = NK[1];
            var A = Array.ConvertAll(Console.ReadLine().Split(' '), long.Parse);

            var DP = new long[42, 2];
            for (int digit = 40; digit >= 0; digit--)
            {
                long sum0 = 0; long sum1 = 0;
                foreach (long a in A)
                {
                    sum0 += (a & ((long)1 << digit)) ^ 0;
                    sum1 += (a & ((long)1 << digit)) ^ ((long)1 << digit);
                }
                DP[digit, 0] = DP[digit + 1, 0] > 0 ? DP[digit + 1, 0] + Math.Max(sum0, sum1) : 0;
                DP[digit, 1] = DP[digit + 1, 1] + ((K & ((long)1 << digit)) > 0 ? sum1 : sum0);
                if ((K & ((long)1 << digit)) > 0)
                {
                    DP[digit, 0] = Math.Max(DP[digit + 1, 1] + sum0, DP[digit, 0]);
                }
            }
            Console.WriteLine(Math.Max(DP[0, 0], DP[0, 1]).ToString());

        }
    }
}


Measured memory_bytes: 32348
n = int(input())
lis = list(map(int,input().split()))
dp = [0] * n

dp[0] = 0
dp[1] = abs(lis[1] - lis[0])

for i in range(n-2):
    a = abs(lis[i+2] - lis[i+1]) + dp[i+1]
    b = abs(lis[i+2] - lis[i]) + dp[i]
    dp[i+2] = min(a,b)
print(dp[n-1]) 

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

using namespace std;

int main (){
  int N,a,sum,minsum;
  bool even;
  
  cin >> N;
  minsum = 100;
  
  for(int i = 0; i < N ; i++){
    even = true;
  	cin >> a;
    sum = 0;
    while(even == true){
      if(a % 2 == 1){
        even = false;
      }
      a /= 2;
      sum++;
    }
    if(minsum > sum){minsum = sum;}
  }
  cout << minsum - 1 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <ctime>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
#include <queue>
#include <utility>
#include <cmath>
#include <functional>
#include <map>
#include <set>
const int INF = 1000000009;

int n;
int px = 0, py = 0;
int pt = 0;
int x, y, t;

int main(){
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		scanf("%d%d%d", &t, &x, &y);
		int mx = std::abs(x - px);
		int my = std::abs(y - py);
		int mt = t - pt;
		//printf("%d\n", mt - mx - my);
		if(mt - mx - my >= 0 && (mt - mx - my) % 2 == 0){
			//printf("pass\n");
			px = x;
			py = y;
			pt = t;
			continue;
		}else{
			printf("No\n");
			return 0;
		}
	}
	printf("Yes\n");
	return 0;
}

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



int cmpfunc (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}


int main() {
    long int n;
scanf("%ld", &n);

long int num[n];

for(long int i=0; i<n; i++) {
    scanf("%ld", &num[i]);
}

 qsort(num, n, sizeof(long int), cmpfunc);
 
 for(long int i=0; i<n-1; i++) {
     if(num[i] == num[i+1]) {
         printf("NO");
         break;
     }
     if(i==(n-2)) {
         printf("YES");
     }
 }
 return 0;
}

Measured memory_bytes: 3324
/*************************************************************************
>>> Author: WindCry1
>>> Mail: lanceyu120@gmail.com
>>> Website: https://windcry1.com
>>> Date: 12/30/2019 11:03:37 PM
*************************************************************************/
//#pragma GCC optimize(3)
//#pragma GCC diagnostic error "-std=c++11"
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <iostream>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <complex>
#include <stack>
#include <bitset>
#include <iomanip>
#include <list>
#include <sstream>
#include <fstream>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define endl '\n'
#define ALL(x) x.begin(),x.end()
#define ll long long
#define ull unsigned long long
#ifdef WindCry1
#define DEBUG(x) cout<<#x<<" : "<<x<<endl;
#endif
#define lowbit(x) x&(-x)
#define ls u<<1
#define rs u<<1|1
using namespace std;
template<typename T> inline T MIN(const T &a,const T &b) {return a<b?a:b;}
template<typename T> inline T MAX(const T &a,const T &b) {return a>b?a:b;}
template<typename T,typename ...Args> inline T MIN(const T &a,const T &b,Args ...args) {return MIN(MIN(a,b),args...);}
template<typename T,typename ...Args> inline T MAX(const T &a,const T &b,Args ...args) {return MAX(MAX(a,b),args...);}
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
const double eps = 1e-8;
const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
pll p[200010];
set<pll> st;
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#ifdef WindCry1
	freopen("C:\\Users\\LENOVO\\Desktop\\in.txt","r",stdin);
#endif
	int n;ll d,a;cin>>n>>d>>a;
	for(int i=1;i<=n;i++){
		cin>>p[i].first>>p[i].second;
	}
	sort(p+1,p+1+n);
	ll sum=0,res=0;
	for(int i=1;i<=n;i++){
		while(!st.empty() and st.begin()->first<p[i].first){
			sum-=st.begin()->second;
			st.erase(st.begin());
		}
		ll temp=max(0LL,(ll)ceil(1.0*(p[i].second-sum)/a));
		res+=temp;
		st.insert(make_pair(p[i].first+2*d,temp*a));
		sum+=temp*a;
		#ifdef WindCry1
			DEBUG(temp);
			DEBUG(res);
			DEBUG(sum);
		#endif 
	}
	cout<<res<<endl;
	return 0;
}



Measured memory_bytes: 15872
using System;

class MinMax {  
  static void Main() {  
    
     string[] str = Console.ReadLine().Split();
     
     int A1 = int.Parse(str[0]);
     int A2 = int.Parse(str[1]);
     int A3 = int.Parse(str[2]);
     int sum = A1 + A2 + A3;

     if(sum >= 22){
       Console.WriteLine("bust");
     }else{
       Console.WriteLine("win");
     }
   }
}

Measured memory_bytes: 13140
#include<bits/stdc++.h>
using namespace std;
#define IO ios_base::sync_with_stdio(false)
#define ll  long long
ll a[3000000];
int main()
{
    IO;
    ll i, j=1, k = 0, mod = 1e18, m, n, n1, m1, l = 0, p, t, h, cnt=0;
    cin>>n;
    for(i=1; i<=n; i++) cin>>a[i];
    sort(a+1,a+n+1);
    for(i=1; i<=n; i++){
        if(a[i]!=0&&j>(1e18/a[i])) return cout<<-1<<endl, 0;
        j*=a[i];
        if(j>mod||j<0) return cout<<-1<<endl, 0;
    }
    cout<<j<<endl;
    return 0;
}


Measured memory_bytes: 4440
# coding: utf-8

class Treasure
  include Math
  def hunt
    x, y = 0, 0
    current_kakudo = 90

    loop do
      hosu, kakudo = gets.chomp.split(",").map {|s| s.to_f}
      break if hosu == 0 && kakudo == 0

      x += hosu * cos(current_kakudo * Math::PI / 180)
      y += hosu * sin(current_kakudo * Math::PI / 180)

      current_kakudo -= kakudo
    end
    print "#{x.to_i}\n#{y.to_i}\n"
  end
end

Treasure.new.hunt

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

using namespace std;
typedef long long li;

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

    int k,x;
    cin>>k>>x;

    li from = max(-1000000, x - k + 1), to = min(1000000, x + k -1);
    for( int i = from; i <= to; ++i)
    {
        cout << i;
        if(i == to)
        {
            cout<<"\n";
        }
        else { cout << " ";}
    }

    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
    vector<int> v(3);
    rep(i,3) cin >> v.at(i);
    sort(v.begin(),v.end());
    int res = (v[1]-v[0]) + (v[2]-v[1]);
    
    cout << res << endl;
}
    
    

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <iomanip>
#include <vector>
#include <cstring>
#include <queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using uld = unsigned long long;


int main(){
    int A;
    cin >> A;
    int ans=A+A*A+A*A*A;


    cout << ans <<endl;

}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define int long long
#define rep(i,x,y) for(int i=x;i<y;i++)
#define repr(i,x,y) for(int i=x;i>=y;i--) 
using namespace std;

void Onigiri()
{
  int a,b,c;
  cin>>a>>b>>c;
  swap(a,b);
  swap(a,c);
  cout<<a<<" "<<b<<" "<<c;
}
signed main()
{
   ios_base::sync_with_stdio(false);cin.tie(NULL);
   #ifdef Zoro
   freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
   #endif  
 
   int t=1; 
   //cin>>t;
 
   while(t--)
   {Onigiri();cout<<"\n";}

   cerr<<"\n"<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms"<<endl;
   return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; //10^19 < 9223372036854775807
typedef unsigned long long ull; //10^20 < 18446744073709551615

#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 

#define MOD 1000000007

ll GCD(ll a, ll b) {
    if (a%b == 0) return b;
    return GCD(b, a%b);
}

int main(void)
{
    ll K;
    cin >> K;

    ll ans = 0;
    FOR (a,1,K) {
        FOR (b,1,K) {
            FOR (c,1,K) {
                ans += GCD(GCD(a,b),c);
            }
        }
    }

    cout << ans << endl;

    return 0;
}


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

signed main(){

  int a[3]; cin >> a[0] >> a[1] >> a[2];
  sort(a,a+3);
  int ans = 0;
  if( !(a[0]%2 == a[1]%2 && a[1]%2 == a[2]%2) ){
    if(a[2]%2 == 0){
      if(a[0]%2 == a[1]%2) ans += 1;
      else ans += 2;
    }
    else {
      if(a[0]%2 == a[1]%2) ans += 1;
      else ans += 2;
    }
  }
  ans += (a[2] - a[1]) / 2 + (a[2] - a[0]) / 2;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
N = int(input())
A = str(input())
B = str(input())
C = str(input())


ans = 0

for i in range(N):
    if A[i] is B[i] and A[i] is C[i]:
        pass
    elif A[i] is B[i] and B[i] is not C[i] and A[i] is not C[i]:
        ans += 1
    elif B[i] is C[i] and B[i] is not A[i] and C[i] is not A[i]:
        ans += 1
    elif A[i] is C[i] and A[i] is not B[i] and C[i] is not B[i]:
        ans += 1
    else:
        ans += 2

print(ans)

Measured memory_bytes: 3064
import sys

input = sys.stdin.readline


def main():
    N, W = [int(x) for x in input().split()]
    WV = [[int(x) for x in input().split()] for _ in range(N)]

    sumv = 0
    for w, v in WV:
        sumv += v

    dp = [[float("inf")] * (sumv + 1) for j in range(N + 1)]

    for i in range(1, N + 1):
        for j in range(sumv + 1):
            w, v = WV[i - 1]
            if j <= v:
                dp[i][j] = min(w, dp[i - 1][j])
            else:
                dp[i][j] = min(dp[i - 1][j], w + dp[i - 1][j - v])

    ans = 0
    for i in range(sumv + 1):
        if dp[N][i] > W:
            break
        else:
            ans = i

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 311552
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx")
#define io_init cin.tie(0);ios::sync_with_stdio(0);cout<<setprecision(10)
#include <bits/stdc++.h>
constexpr int INF = 2147483647;
constexpr long long int INF_LL = 9223372036854775807;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

int main() {
	io_init;
	int N, M;
	cin >> N >> M;
	string S;
	cin >> S;
	vector<int> ans;
	for (int i = N; i > 0; ) {
		bool flag = false;
		for (int j = max(i - M, 0); j < i; j++) {
			if (S[j] == '0') {
				ans.push_back(i - j);
				i = j;
				flag = true;
				break;
			}
		}
		if (!flag) {
			cout << -1 << endl;
			return 0;
		}
	}
	reverse(ans.begin(), ans.end());
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << " ";
	}
	cout << endl;
}

Measured memory_bytes: 1096
#include<bits/stdc++.h>
#define fo(i,a,b)for(int i=a,_e=b;i<=_e;++i)
#define ll long long
using namespace std;
const int N=1e6+5,mo=1e9+7,mo3=(mo+1)/3;
int n,iv[N],ans;
int main(){
	cin>>n;
	iv[1]=1;
	fo(i,2,n)iv[i]=mo-(ll)iv[mo%i]*(mo/i)%mo;
	for(int i=1,s=1;s=(ll)s*mo3%mo,i<=n;++i)ans=((ll)iv[n-i+1]*s+ans)%mo;
	cout<<(ll)ans*iv[n]%mo;
}

Measured memory_bytes: 4096
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
    	
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int H = sc.nextInt();
		int W = sc.nextInt();

		String A[][] = new String[H][W];
		for(int i = 0;i < H;i++){
			String IN = sc.next();
			for(int j= 0;j < W;j++){
				A[i][j] = IN.substring(j, j+1); 
			}
		}
		
		for(int i = 0;i < H;i++){
			int cnt = 0;
			for(int j = 0;j < W;j++){
				if(A[i][j].equals(".")){
					cnt ++;
				}
			}
			if(cnt == W){
				H --;
				for(int k = i;k < H;k++){
					for(int j = 0;j < W;j++){
						A[k][j] = A[k+1][j];
					}
				}
				i --;
			}
		}

		for(int j = 0;j < W;j++){
			int cnt = 0;
			for(int i = 0;i < H;i++){
				if(A[i][j].equals(".")){
					cnt ++;
				}
			}
			if(cnt == H){
				W --;
				for(int k = j;k < W;k++){
					for(int i = 0;i < H;i++){
						A[i][k] = A[i][k+1];
					}
				}
				j --;
			}
		}

		for(int i = 0;i < H;i++){
			String ans = "";
			for(int j = 0;j < W;j++){
				ans = ans + A[i][j]; 
			}
			System.out.println(ans);
		}
		
   		sc.close();
        return ;

    }
    
}



Measured memory_bytes: 28372
#include<stdio.h>
#define N 101

struct Card{
  char s;
  char v;
};

void bubble(struct Card data[],int n)
{
  int i,j;
  struct Card tmp;

  for(i=0; i<n; i++){
    for(j=n-1; j>=i+1; j--){
      if(data[j].v < data[j-1].v){
        tmp = data[j];
        data[j] = data[j-1];
        data[j-1] = tmp;
      }
    }
  }
}

void selection(struct Card data[], int n)
{
  int i,j,mini;
  struct Card tmp;

  for(i=0; i<n; i++){
    mini = i;
    for(j=i; j<n; j++){
      if(data[j].v < data[mini].v)
        mini = j;
    }
    tmp = data[i];
    data[i] = data[mini];
    data[mini] = tmp;
  }
}

void print(struct Card data[], int n)
{
  int i;

  for (i=0; i<n-1; i++){
    printf("%c%c ",data[i].s,data[i].v);
  }
  printf("%c%c\n",data[n-1].s,data[n-1].v);
}

int isStable(struct Card C1[], struct Card C2[], int n)
{
  int i;

  for(i=0; i<n; i++){
    if(C1[i].s != C2[i].s)
      return 0;
  }

  return 1;
}

int main()
{
  int n,i;
  char ch;
  struct Card C1[N], C2[N];

  scanf("%d\n",&n);

  for (i=0; i<n; i++)
    scanf("%c%c ",&C1[i].s,&C1[i].v);

  for (i= 0; i<n; i++)
    C2[i] = C1[i];

  bubble(C1,n);
  selection(C2,n);
  print(C1,n);

  printf("Stable\n");

  print(C2,n);

  if(isStable(C1,C2,n))
    printf("Stable\n");
  else
    printf("Not stable\n");

  return 0;
}


Measured memory_bytes: 2056
#include <iostream>

using namespace std;

int main(){
  int a, b;
  cin >> a >> b;

  if (a > b){
    cout << "a > b" << endl;
  }
  else if (a < b){
    cout << "a < b" << endl;
  }
  else if (a == b){
    cout << "a == b" << endl;
  }
  return 0;
}

Measured memory_bytes: 3076
#include <stdio.h>
#include <stdlib.h>

void CountingSort(int *,int *,int *,int,int);

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

Measured memory_bytes: 16056
#include <bits/stdc++.h>
#define foi(i,k,n) for(int i = (int)k; i < (int)n; ++i)
using namespace std;
using ll = long long;
using ii = pair<int,int>;

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  int h1,m1,h2,m2,k;
  cin >> h1 >> m1 >> h2 >> m2 >> k;
  int addh = k/60, addm = k%60;
  h1 += addh;
  m1 += addm;

  if (m1 >= 60) {
    h1++;
    m1 -= 60;
  }

  if (h1 < h2 || (h1 == h2 && m1 <= m2)) {
      cout << 60*(h2-h1) + m2-m1 << '\n';
  } else {
    cout << 0 << '\n';
  }
  return 0;
}


Measured memory_bytes: 3612
import java.io.IOException;
import java.math.BigInteger;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static Map<BigInteger, Integer> memo;
    static boolean[][] vis;
    static List<List<Integer>> adj;
    static List<Integer> vertices;

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

        int n = sc.nextInt();
        int[] occ = new int[n+1];

        for (int i = 1; i < n; ++i) {
            occ[sc.nextInt()]++;
        }

        for(int i =1; i < occ.length; ++i){
            System.out.println(occ[i]);
        }
    }


    static int lowerBound(int[] arr, int element) {

        int low = 0, high = arr.length - 1, ans = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] <= element) {
                low = mid + 1;
                ans = mid;
            } else
                high = mid - 1;

        }

        return high;
    }

    static boolean isPalindrome(String word) {
        int i = 0, j = word.length() - 1;

        while (i <= j) {
            if (word.charAt(i++) != word.charAt(j--))
                return false;
        }

        return true;
    }

    static String longestPalindrome(String[] words, String word, int i) {
        if (i >= words.length) {
            if (isPalindrome(word))
                return word;

            return "";
        }

        if (word.length() > 0 && isPalindrome(word))
            return word;
        String left = longestPalindrome(words, word + words[i], i + 1);
        String right = longestPalindrome(words, word, i + 1);

        if (left.length() > 0)
            return left;
        return right;
    }


    static int solve(int[] arr, int i, int j, int k) {
        if (i == j && arr[i] <= k)
            return 1;

        int left = 0, right = 0;
        if (arr[i] <= k)
            left = solve(arr, i + 1, j, k) + 1;

        else if (arr[j] <= k)
            right = solve(arr, i, j - 1, k) + 1;

        return left + right;
    }

    static int minMove(BigInteger bg, int count) {
        if (bg.equals(BigInteger.ONE))
            return count;

        int first = Integer.MAX_VALUE, sec = Integer.MAX_VALUE, last = Integer.MAX_VALUE;
        if (bg.mod(BigInteger.valueOf(2)).compareTo(BigInteger.ZERO) == 0)
            first = minMove(bg.divide(BigInteger.valueOf(2)), count + 1);

        else if (bg.mod(BigInteger.valueOf(3)).compareTo(BigInteger.ZERO) == 0)
            sec = minMove(bg.multiply(BigInteger.valueOf(2)).divide(BigInteger.valueOf(3)), count + 1);

        else if (bg.mod(BigInteger.valueOf(5)).compareTo(BigInteger.ZERO) == 0)
            last = minMove(bg.multiply(BigInteger.valueOf(4)).divide(BigInteger.valueOf(5)), count + 1);

        if (memo.containsKey(bg))
            return memo.get(bg);

        memo.put(bg, Math.min(first, Math.min(sec, last)));

        return Math.min(first, Math.min(sec, last));
    }
}


Measured memory_bytes: 69500
h, n = map(int, input().split())
a, b = [], []
for i in range(n):
    a_, b_  = map(int, input().split())
    a.append(a_)
    b.append(b_)
dp = [0] * (max(a) + h)
for i in range(1, max(a) + h):
    dp[i] = min(dp[i - a[j]] + b[j] for j in range(n))
print(min(dp[h:]))

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

using namespace std;

#define int long long

int mod = 1e9 + 7;

signed main() {
	int n; cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	vector<int> sum(n);
	int prev = 0;
	for (int i = 0; i < n; ++i) {
		sum[i] = prev + a[i];
		sum[i] %= mod;
		prev = sum[i];
	}
	long long res = 0;
	for (int i = n-1; i > 0; --i) {
		res += a[i] * sum[i-1];
		res %= mod;
	}
	cout << res << endl;
}


Measured memory_bytes: 6320
import java.util.BitSet;
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		while(true){
			int n = in.nextInt();
			if(n == 0) break;
			BitSet[] sche = new BitSet[30];
			for(int i=0; i<30; i++){
				sche[i] = new BitSet(n);
			}
			long[] map = new long[n];
			for(int i=0; i<n; i++){
				map[i] = 1L<<i;
				int f = in.nextInt();
				for(int j=0; j<f; j++){
					int day = in.nextInt();
					sche[day-1].set(i);
				}
			}
			long all = (1L<<n)-1;
			int res = -1;
			out: for(int i=0; i<30; i++){
				for(int j=sche[i].nextSetBit(0); j!=-1; j=sche[i].nextSetBit(j+1)){
					for(int k=sche[i].nextSetBit(0); k!=-1; k=sche[i].nextSetBit(k+1)){
						if(j == k) continue;
						map[j] |= map[k];
					}
					if(map[j] == all){
						res = i+1;
						break out;
					}
				}
			}
			System.out.println(res);
		}
	}
}

Measured memory_bytes: 69772
#include <bits/stdc++.h>
using namespace std;
int v[200200];
int ctr;
int main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	ctr = 0;
	cin >> n;
	for(int i=0;i<n;i++) {
		int t;
		cin >> t;
		v[i] = t;
	}
	int s = 1,e=n;
	int ls = n;
	while(s <= e) {
		map<int,int> mp;
		int m = (s+e)/2;
		bool po = true;
		for(int i=0;i<n-1;i++) {
			if(v[i+1] <= v[i]) {
				for(auto it = mp.rbegin();it != mp.rend() && it->first > v[i+1];) {
					mp.erase(it->first);
					it = mp.rbegin();
				}
				mp[v[i+1]]++;
				int id = v[i+1];
				while(id > 0 && mp[id] >= m) {
					if(m == 1) {po = false;break;}
					mp[id] -= m;
					mp[--id]++;
				}
				if(mp[0] > 0) {po = false;break;}
			}
			if(!po) break;
		}
		if(po) {
			ls = m;e = m-1;
		} else {
			s = m+1;
		}
	}
	printf("%d\n",ls);
}


Measured memory_bytes: 1024
import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  s=S()
  x=len(s)

  ans=['x' for _ in range(x)]
  return ''.join(ans)

# main()
print(main())


Measured memory_bytes: 5716
use proconio::{input, fastout};

#[fastout]
fn main() {
  input!{
    mut x:i128,
    k:i128,
    d:i128
  }
  x = x.wrapping_abs();
  let nk = k - (x/d);
  println!("{}",
                if nk >= 0{
                    if nk%2 == 0 {
                        x - (x/d)*d
                    } else {
                        ((x-(x/d)*d)-d).wrapping_abs()
                    }
                } else {
                    x - k*d
                }
           );
}


Measured memory_bytes: 2184
def warshall_floyd(v_count: int, matrix: list) -> list:
    """ ワーシャルフロイド
    :param v_count: 頂点数
    :param matrix: 隣接行列(到達不能はfloat("inf"))
    """
    # 到達不能をfloat("inf")にしておけば余計なチェックを入れなくても
    # inf > inf+(-1) のような到達不能＋負辺が繋がってしまうことはない
    for i in range(v_count):
        for j, c2 in enumerate(row[i] for row in matrix):
            for k, (c1, c3) in enumerate(zip(matrix[j], matrix[i])):
                if c1 > c2+c3:
                    matrix[j][k] = c2+c3
    return matrix

while True:
    e_count, v_count = map(int, input().split())
    if not e_count:
        break
    inf = float("inf")
    edges_cost, edges_time = [[inf]*v_count for _ in [0]*v_count], [[inf]*v_count for _ in [0]*v_count]
    for _ in [0]*e_count:
        a, b, cost, time = map(int, input().split())
        a, b = a-1, b-1
        edges_cost[a][b] = cost
        edges_cost[b][a] = cost
        edges_time[a][b] = time
        edges_time[b][a] = time

    warshall_floyd(v_count, edges_cost)
    warshall_floyd(v_count, edges_time)

    for _ in [0]*int(input()):
        p, q, r = map(int, input().split())
        print((edges_time if r else edges_cost)[p-1][q-1])


Measured memory_bytes: 6208
#include <bits/stdc++.h>
#define f first
#define s second

using namespace std;

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

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int h, w;
    cin >> h >> w;
    int k;
    cin >> k;
    vector<vector<char>> F(h, vector<char>(w));
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            cin >> F[i][j];
        }
    }
    int cnt = 0;
    for(int m1 = 0; m1 < (1 << h); m1++) {
        for(int m2 = 0; m2 < (1 << w); m2++) {
            int cur_k = 0;
            for(int i = 0; i < h; i++) {
                for(int j = 0; j < w; j++) {
                    if(((m1 >> i) & 1) || ((m2 >> j) & 1)) {
                        continue;
                    }
                    cur_k += (F[i][j] == '#');
                }
            }
            cnt += (cur_k == k);
        }
    }
    cout << cnt << '\n';
    return 0;
}


Measured memory_bytes: 3612
def main():
    from collections import deque
 
    n,m =map(int,input().split())
    abl=[[] for i in range(n+1)]
    for i in range(m):
        a,b = map(int,input().split())
        abl[a].append(b)
        abl[b].append(a)
 
    an=[0]*(n+1)
    an[0]=1
    tg = deque([1])
    while len(tg):
        itg = tg.popleft()
        for j in abl[itg]:
            if an[j]==0:
                an[j]=itg
                tg.append(j)

    if all(an):
        print('Yes')
        for j in an[2:]:
            print(j)
    else:
        print('No')
 
main()

Measured memory_bytes: 34532
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
typedef long long ll;
using namespace std;
int main(){
  string s;
  cin >> s;
  if(s == "Sunny"){ s = "Cloudy";
  }else if(s == "Cloudy"){ s = "Rainy";
  }else{
      s = "Sunny";
  }
  cout << s <<endl;
}



Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = ReadInt();
            var p = ReadArrayInt();
            var cnt = 0;
            var suc = true;
            for (int i = 0; i < N; i++)
            {
                if (p[i] != (i + 1)) cnt++;
                if (cnt > 2)
                {
                    suc = false;
                    break;
                }
            }

            Console.WriteLine(suc ? "YES" : "NO");
            Console.ReadLine();
        }

        static string Read() { return Console.ReadLine(); }
        static int ReadInt() { return int.Parse(Read()); }
        static long ReadLong() { return long.Parse(Read()); }
        static int[] ReadArrayInt() { return Read().Split(' ').Select(s => int.Parse(s)).ToArray(); }
        static long[] ReadArrayLong() { return Read().Split(' ').Select(s => long.Parse(s)).ToArray(); }
    }
}

Measured memory_bytes: 13396