akhauriyash/Code-Regression huggingface dataset:
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).ok();
    let mut it = buf.split_whitespace();
    let n = it.next().unwrap().parse::<i64>().unwrap();
    let x = it.next().unwrap().parse::<i64>().unwrap();
    let mut t = Vec::new();
    let mut aoki = 0;
    for _ in 0..n {
        let b = it.next().unwrap().parse::<i64>().unwrap();
        let l = it.next().unwrap().parse::<i64>().unwrap();
        let u = it.next().unwrap().parse::<i64>().unwrap();
        let mx = b * l + (x - b) * u;
        aoki += b * l;
        t.push((b, l, u, mx));
    }
    t.sort_by_key(|a| -a.3);
    let mut low = -1;
    let mut high = n * x;
    while high - low > 1 {
        let mid = (low + high) / 2;
        let thr = (mid / x) as usize;
        let y = mid % x;
        let mut sum = 0;
        for i in 0..thr { sum += t[i].3 }
        let mut best = 0;
        for i in 0..n as usize {
            let mut cur = sum;
            if i < thr {
                cur += t[thr].3 - t[i].3;
            }
            cur += std::cmp::min(t[i].0, y) * t[i].1 + std::cmp::max(0, y - t[i].0) * t[i].2;
            best = std::cmp::max(best, cur);
        }
        if best >= aoki {
            high = mid;
        } else {
            low = mid;
        }
    }
    println!("{}", high);
}


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

int main ()
{
    int x, a, b;
    cin >> x >> a >> b;
    if (abs(x-a) < abs (x-b)){
        cout << "A";
    }
    else
        cout << "B";

    return 0;
}



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

int main() {
    int n, m, x, y; cin >> n >> m >> x >> y;
    vector<int> xs(n + 1), ys(m + 1);
    for (int i = 0; i < n; i++) { cin >> xs.at(i); }
    for (int i = 0; i < m; i++) { cin >> ys.at(i); }
    xs.at(n) = x; ys.at(m) = y;
    sort(xs.rbegin(), xs.rend());
    sort(ys.begin(), ys.end());
    if (xs.at(0) < ys.at(0)) cout << "No War";
    else cout << "War";
    cout << endl;
}

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

int main(){
  string S;
  cin >>S;
 
  int ans = 999;
  int L = S.size();
  rep(i,0,L-3){
    string s = S.substr(i,3);
    int d = abs(753-stoi(s));
    ans = min(d,ans);
  }
  cout <<ans<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <array>
#include <bitset>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
typedef long long lint;

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    lint a, b, q;
    cin >> a >> b >> q;
    vector<lint> s(a+2);
    vector<lint> t(b+2);
    const lint INF = 1000000000000000;
    s[0] = -INF;
    s[a+1] = INF;
    t[0] = -INF;
    t[b+1] = INF;
    vector<lint> x(q);
    for (int i=0; i<a; ++i){
        cin >> s[i+1];
    }
    for (int i=0; i<b; ++i){
        cin >> t[i+1];
    }
    for (int i=0; i<q; ++i){
        cin >> x[i];
    }
    vector<lint> ans(8, INF);
    for (int i=0; i<q; ++i){
        for (int j=0; j<8; ++j){
            ans[j] = INF;
        }
        auto itr_a = lower_bound(s.begin(), s.end(), x[i]);
        auto itr_b = lower_bound(t.begin(), t.end(), x[i]);
        int a_num, b_num;
        a_num = (int)(itr_a - s.begin());
        b_num = (int)(itr_b - t.begin());
        // cout << a_num << " " << b_num << endl;
        /*
        cout << s[a_num - 1] << ", " << s[a_num] << ", " << s[a_num + 1] << endl;
        cout << t[b_num - 1] << ", " << t[b_num] << ", " << t[b_num + 1] << endl;
        */
        // cal
        // case 1:
        ans[0] = abs(x[i] - s[a_num - 1]) + abs(s[a_num - 1] - t[b_num - 1]);
        ans[1] = abs(x[i] - t[b_num - 1]) + abs(t[b_num - 1] - s[a_num - 1]);
        // case 2:
        ans[2] = abs(x[i] - s[a_num - 1]) + abs(s[a_num - 1] - t[b_num]);
        ans[3] = abs(x[i] - t[b_num]) + abs(t[b_num] - s[a_num - 1]);
        // case 3:
        ans[4] = abs(x[i] - t[b_num - 1]) + abs(t[b_num - 1] - s[a_num]);
        ans[5] = abs(x[i] - s[a_num]) + abs(s[a_num] - t[b_num - 1]);
        // case 4:
        ans[6] = abs(x[i] - s[a_num]) + abs(s[a_num] - t[b_num]);
        ans[7] = abs(x[i] - t[b_num]) + abs(t[b_num] - s[a_num]);
        /*
        for (int j=0; j<8; ++j){
            cout << ans[j] << " ";
        }
        cout << endl;
        */
        sort(ans.begin(), ans.end());
        cout << ans[0] << endl;
    }
    return 0;
}

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

int main() {
    int N,K;
    cin >> N >> K;
    vector<int> x(N);
    for(int i=0;i<N;i++){
        cin >> x.at(i);
    }
    int move_sum = 0;
    for(int i=0;i<N;i++){
        int A = 2*abs(x.at(i));
        int B = 2*abs(x.at(i)-K);
        if(A >= B){
            move_sum += B;
        }
        else{
            move_sum += A;
        }
    }
    cout << move_sum << endl;
    return 0;
}

Measured memory_bytes: 256
// finish date: 2018/02/24

#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <climits>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvvi vector<vector<vector<int>>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vvd vector<vector<double>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vs vector<string>
#define vc vector<char>
#define vvc vector<vector<char>>
#define bigmod 1000000007
#define INF 1050000000
#define pii pair<int,int>


int main() {
    int N;
    cin >> N;
    map<int, int> odd, even;

    vi A(N);
    rep(i, N) {
        cin >> A[i];
        if (i % 2 == 0) odd[A[i]]++;
    }
    sort(A.begin(), A.end());
    int c = 0;
    rep(i, N) {
        if (i % 2 == 0 && !odd.count(A[i])) c++;
    }
    cout<<c<<endl;
    int in;
    bool smallerIsOddMap = true;

//    while(!even.empty()){
//        bool con1 = smallerIsOddMap&&(odd.begin()->first<=even.begin()->first);
//        bool con2 = !smallerIsOddMap&&(odd.begin()->first>even.begin()->first);
//        bool con3 = smallerIsOddMap&&(odd.begin()->first>even.begin()->first);
//        bool con4 = !smallerIsOddMap&&(odd.begin()->first<even.begin()->first);
//        if(con1||con2){
//            odd.erase(odd.begin()->first);
//            even.erase(even.begin()->first);
//        }else if(con3){
//            c++;
//        }else{
//            c++;
//        }
//    }

    return 0;
}





Measured memory_bytes: 2944
import itertools
import numpy as np

N, M, X = map(int, input().split())
lis_all = [list(map(int, input().split())) for _ in range(N)]

lis_C = np.array(list(map(lambda x: x[0], lis_all)))
lis_A = np.array(list(map(lambda x: x[1:], lis_all)))

row_idx = []
bools = [True,False]
for boollis in itertools.product(bools, repeat=N):
    row_idx.append(list(boollis))


c_min = lis_C.sum()+100
for i in range(len(row_idx)):
    if all(lis_A[row_idx[i]].sum(axis=0) >= X):
        c_min = min(lis_C[row_idx[i]].sum(), c_min)
if c_min > lis_C.sum():
    ans = -1
else :
    ans = c_min
print(ans)

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

int main(){
  int64_t a,v;
  cin >>a>>v;
  int64_t b,w;
  cin>>b>>w;
  int64_t t;
  cin >>t;
  if(v<=w){
    cout <<"NO"<<endl;
    return 0;
  }
  if((double)abs(a-b)/(v-w)<=t){
    cout <<"YES"<<endl;
  }
  else
    cout <<"NO"<<endl;
}

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

#define ll long long
#define ull unsigned long long
#define db long double
#define pb push_back
#define ppb pop_back
#define F first
#define S second
#define mp make_pair
#define all(x) (x).begin(), (x).end()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

int a[200007];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	
	int n;
	cin >> n;
	for (int i = 1; i < n; i++) {
		int x;
		cin >> x;
		a[x]++;
	}
	for (int i = 1; i <= n; i++) {
		cout << a[i] << '\n';
	}
}


Measured memory_bytes: 4360
#include<bits/stdc++.h>
using namespace std ;
int main()
{
    int n ;
    cin >> n ;
    string s ;
    cin >> s ;
    int maxi = 0 ;
    int cnt =0 ;
    for(int i =0 ; i < s.size() ; i++)
    {
        if(s[i] == 'I')
            cnt++ ;
        else
            cnt-- ;
        if(cnt >maxi)
            maxi = cnt ;
    }
    cout << maxi << endl ;

}


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

int main() {
  int H,W;
  cin >> H >> W;
  vector<vector<char>> S(H,vector<char>(W));
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin >> S.at(i).at(j);
    }
  }
  
  vector<int> max(H*W);
  vector<vector<int>> dist(H*W,vector<int>(H*W,-1));
  vector<queue<int>> que(H*W);
  
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(S.at(i).at(j)!='.') continue;
      dist.at(i*W+j).at(i*W+j)=0;
      que.at(i*W+j).push(i*W+j);
      
      while(!que.at(i*W+j).empty()){
        int v=que.at(i*W+j).front();
        int J=v%W;
        int I=(v-J)/W;
        que.at(i*W+j).pop();
        
          if(I!=0){
            if(S.at(I-1).at(J)=='.' && dist.at(i*W+j).at(W*(I-1)+J)==-1){
              dist.at(i*W+j).at(W*(I-1)+J)=dist.at(i*W+j).at(W*I+J)+1;
              que.at(i*W+j).push(W*(I-1)+J);
            }
          }
          if(I!=H-1){
            if(S.at(I+1).at(J)=='.' && dist.at(i*W+j).at(W*(I+1)+J)==-1){
              dist.at(i*W+j).at(W*(I+1)+J)=dist.at(i*W+j).at(W*I+J)+1;
              que.at(i*W+j).push(W*(I+1)+J);
            }
          }
          if(J!=0){
            if(S.at(I).at(J-1)=='.' && dist.at(i*W+j).at(W*I+J-1)==-1){
             dist.at(i*W+j).at(W*I+J-1)=dist.at(i*W+j).at(W*I+J)+1;
             que.at(i*W+j).push(W*I+J-1);
            }
          }
          if(J!=W-1){
            if(S.at(I).at(J+1)=='.' && dist.at(i*W+j).at(W*I+J+1)==-1){
             dist.at(i*W+j).at(W*I+J+1)=dist.at(i*W+j).at(W*I+J)+1;
             que.at(i*W+j).push(W*I+J+1);
            }
          }  
      }
      
      sort(dist.at(i*W+j).begin(),dist.at(i*W+j).end());
      reverse(dist.at(i*W+j).begin(),dist.at(i*W+j).end());
      max.at(i*W+j)=dist.at(i*W+j).at(0);
      
    }
  }
  sort(max.begin(),max.end());
  reverse(max.begin(),max.end());
  cout << max.at(0) << endl;
}

Measured memory_bytes: 1152
#include <stdio.h>
#include <stdlib.h>
#include <string.h> // 文字列処理の関数
#include <ctype.h> // 文字変換(大文字/小文字)の関数

int main() {
char buf[10];
scanf("%s",buf);
if (buf[0]=='Y' && buf[1]=='A' && buf[2]=='K' && buf[3]=='I')
 printf("Yes\n");
else
 printf("No\n");
return 0;
}

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

int main() {
	long long int N;
	cin >> N;
	cout << N << ":";
	if( N <= 1 ) {
		cout << " " << N << endl;
		return 0;
	}
	long long int M = sqrtl( N ) + 1;
	for( size_t i = 2; i <= M; i++ ) {
		while( N%i == 0 ) {
			cout << " " << i;
			N /= i;
		}
	}
	if( N != 1 ) {
		cout << " " << N;
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 3096
using System;

namespace atCoder
{
    class Program
    {
        static void Main()
        {
            int a = int.Parse(Console.ReadLine());
            string s = Console.ReadLine();

            if (3200 <= a)
            {
                Console.WriteLine(s);
            }
            else
            {
                Console.WriteLine("red");
            }
        }
    }
}

Measured memory_bytes: 11092
#include <cstdio>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#define rep(i,a,n) for(int i=a; i<n; i++)
using namespace std;

// 移動元と行先と辺のコストを記録する構造体
template <typename T>
struct Edge {
    int from, to;
    T cost;
    Edge(int s, T d) : to(s), cost(d) {}
    Edge(int f, int s, T d) : from(f), to(s), cost(d) {}

    bool operator<(const Edge &e) const {
        return cost < e.cost;
    }
    bool operator>(const Edge &e) const {
        return cost > e.cost;
    }
};

template <typename T>
using Graph = vector< vector< Edge<T> > >;

template <typename T>
vector<int> tpsort_Kahn(const vector< vector< Edge<T> > > &g) {
    const int V = g.size();
    vector<int> indeg(V, 0);
    stack<int> S;

    rep(i,0,V) rep(j,0,g[i].size())
        indeg[ g[i][j].to ]++;
    rep(i,0,V) if(indeg[i] == 0) S.push(i);

    vector<int> ans;
    while(S.size() > 0) {
        int u = S.top(); S.pop();
        ans.push_back(u);
        rep(i,0,g[u].size()) {
            indeg[ g[u][i].to ]--;
            if(indeg[ g[u][i].to ] ==  0)
                S.push( g[u][i].to );
        }
    }
    return ans;
}


int main() {
    int N;
    while(cin >> N, N) {
        vector<string> vs(N);
        for(int i=0; i<N; i++) {
            cin >> vs[i];
        }

        bool ok = true;
        Graph<int> G(26);
        for(int i=0; i<N; i++) {
            for(int j=i+1; j<N; j++) {
                int S = min(vs[i].length(), vs[j].length());
                bool differ = false;
                for(int k=0; k<S; k++) {
                    if(vs[i][k] != vs[j][k]) {
                        differ = true;
                        int u = vs[i][k] - 'a', v = vs[j][k] - 'a';
                        G[u].push_back(Edge<int>(v, 1));
                        break;
                    }
                }
                if(!differ && vs[i].length() > vs[j].length()) ok = false;
            }
        }
        
        if(tpsort_Kahn(G).size() == 26 && ok) cout << "yes" << endl;
        else cout << "no" << endl;
    }
    return 0;
}


Measured memory_bytes: 5820
def main():
    import sys
    input = sys.stdin.readline


    #Union Find

    #xの根を求める
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    #xとyの属する集合の併合
    def unite(x,y):
        x = find(x)
        y = find(y)
        
        if x == y:
            return False
        else:
            #sizeの大きいほうがx
            if par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True

    #xとyが同じ集合に属するかの判定
    def same(x,y):
        return find(x) == find(y)

    #xが属する集合の個数
    def size(x):
        return -par[find(x)]

    n,m = map(int,input().split())
    #初期化
    #根なら-size,子なら親の頂点
    par = [-1]*n

    for i in range(m):
        X,Y = map(int,input().split())
        unite(X-1,Y-1)
    
    #tank = set([])
    for i in range(n):
        find(i)
    ans=0
    for i in par:
        if i<0:
            ans=max(ans,-i)
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 14600
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double ld;
#define vec(s) vector

#define vvec(s) vector<vector
>
typedef vector<lli> vi;
typedef vector<vi> vvi;
typedef pair<lli,lli> pii;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Yes(x) cout<<(x?"Yes":"No")<<endl;
#define YES(x) cout<<(x?"YES":"NO")<<endl;
#define out(s) cout<<s<<endl;
#define Reverse(x) reverse(all(x));
#define Sort(x) sort(all(x));
#define pb(s) push_back(s);
#define sp " " 
#define INF 10000000000
#define LINF 9000000000000000000
#define all(s) s.begin(),s.end()
void vout(vi v){
    for(lli i=0;i<v.size();i++)
    cout<<v.at(i)<<endl;
}
int main(){
    cout << std::fixed << std::setprecision(10);
    lli n;
    cin >> n;
    vi a(n);
    rep(i,n){
        cin >> a[i];
    }
    lli ma = a[0];
    lli ans = 0;
    for (lli i = 1; i < n;i++){
        if(ma<a[i]){
            ma=a[i];
        }
        else{
            ans += ma - a[i];
        }
    }
    out(ans);
}

Measured memory_bytes: 4768
#include<bits/stdc++.h>
using namespace std;
int main () {
int H, N ,i,X;
vector<int> A;
cin>>H ;
cin>>N;
A.reserve(N);

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

if(H>0){cout<<"No";}
else{cout<<"Yes"; }
}


Measured memory_bytes: 640
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

//#define LOCAL 0
//#ifdef LOCAL
//#define DEBUG(s) cout << (s) << endl
//#define dump(x)  cerr << #x << " = " << (x) << endl
//#define BR cout << endl;
//#else
//#define DEBUG(s) do{}while(0)
//#define dump(x) do{}while(0)
//#define BR
//#endif


//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30)
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007
//ここから編集する
int tax(int p,int x){
    return p * (100 + x) / 100;
}
void solve(int x,int y,int s){
    int ans = -1;
    for(int i = 1; i < s; ++i){
        for(int j = 1; j < s; ++j){
            if(tax(i,x) + tax(j,x) == s){
                ans = max(ans,tax(i,y) + tax(j,y));
            }
        }
    }
    cout << ans << endl;
}

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

    while(true){
        int x,y,s;
        cin >> x >> y >> s;
        if(x == 0) return 0;
        solve(x,y,s);
    }


    return 0;
}



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

int main() {
	int n;
	cin>>n;
	vector<int>h(n);
	for(int i = 0 ; i < n ; i++) cin>>h[i];
	if(n == 1) cout<<0<<endl;
	else{
	    vector<int>dp(n);
    	dp[0] = 0;
    	dp[1] = abs(h[1] - h[0]);
    	for(int j = 2 ; j < n ; j++){
    	    dp[j] = min(dp[j-1]+abs(h[j] - h[j-1]) , dp[j-2] + abs(h[j] - h[j-2]));
    	}
    	cout<<dp[n-1]<<endl;   
	}
	return 0;
}


Measured memory_bytes: 1024
#ifndef ___CLASS_MODINT
#define ___CLASS_MODINT

#include <cstdint>

template<std::uint32_t mod>
class modint {
private:
	std::uint32_t n;
public:
	modint() : n(0) {};
	modint(std::uint64_t n_) : n(n_ % mod) {};
	bool operator==(const modint& m) const { return n == m.n; }
	bool operator!=(const modint& m) const { return n != m.n; }
	std::uint32_t get() const { return n; }
	modint& operator+=(const modint& m) { n += m.n; n = (n < mod ? n : n - mod); return *this; }
	modint& operator-=(const modint& m) { n += mod - m.n; n = (n < mod ? n : n - mod); return *this; }
	modint& operator*=(const modint& m) { n = std::uint64_t(n) * m.n % mod; return *this; }
	modint operator+(const modint& m) const { return modint(*this) += m; }
	modint operator-(const modint& m) const { return modint(*this) -= m; }
	modint operator*(const modint& m) const { return modint(*this) *= m; }
	modint binpow(std::uint64_t b) const {
		modint ans = 1, m = modint(*this);
		while (b) {
			if (b & 1) ans *= m;
			m *= m;
			b >>= 1;
		}
		return ans;
	}
	modint inv() { return (*this).binpow(mod - 2); }
};

#endif // ___CLASS_MODINT

#include <vector>
#include <iostream>
using namespace std;
using modulo = modint<1000000007>;
int main() {
	int N, Q;
	cin >> N >> Q;
	vector<int> A(N);
	for (int i = 0; i < N; ++i) cin >> A[i];
	vector<int> X(Q), Y(Q);
	for (int i = 0; i < Q; ++i) {
		cin >> X[i] >> Y[i]; --X[i], --Y[i];
	}
	vector<vector<modulo> > dp(N, vector<modulo>(N));
	for (int i = 0; i < N; ++i) {
		for (int j = i + 1; j < N; ++j) {
			dp[i][j] = 1;
		}
	}
	modulo inv2 = modulo(2).inv();
	for (int i = Q - 1; i >= 0; --i) {
		modulo SS = (dp[X[i]][Y[i]] + dp[Y[i]][X[i]]) * inv2;
		dp[X[i]][Y[i]] = SS;
		dp[Y[i]][X[i]] = SS;
		for (int j = 0; j < N; ++j) {
			if (j == X[i] || j == Y[i]) continue;
			modulo S1 = (dp[X[i]][j] + dp[Y[i]][j]) * inv2;
			dp[X[i]][j] = S1;
			dp[Y[i]][j] = S1;
			modulo S2 = (dp[j][X[i]] + dp[j][Y[i]]) * inv2;
			dp[j][X[i]] = S2;
			dp[j][Y[i]] = S2;
		}
	}
	modulo ex = 0;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (A[i] > A[j]) ex += dp[i][j];
		}
	}
	modulo ans = ex * modulo(2).binpow(Q);
	cout << ans.get() << endl;
	return 0;
}

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

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  
  while (A > 0 && C > 0) {
   C = C - B;
   A = A - D;
  }
  
  if (C > 0) {
    cout << "No" << endl;
  }
  else {
    cout << "Yes" << endl;
  }
  
} 

Measured memory_bytes: 3632
#include<stdio.h>

int main(void)
{
	int n,i,b;
	
	scanf("%d",&n);
	int a[100001];
	for(i=1;i<=n;i++){
		scanf("%d",&b);
		a[b]=i;
	}
	
	for(i=1;i<=n;i++)
		printf("%d ",a[i]);
	return 0;
}

Measured memory_bytes: 1152
package main

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

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, math.MaxInt64)
}

func readInt() int {
	sc.Scan()
	r, _ := strconv.Atoi(sc.Text())
	return r
}

func main() {
	n, m := readInt(), readInt()
	a := make([]int, m)
	b := make([]int, m)
	hash := make([]int, n)
	for i := 0; i < m; i++ {
		a[i], b[i] = readInt(), readInt()
		hash[a[i]-1]++
		hash[b[i]-1]++
	}
	for _, v := range hash {
		fmt.Println(v)
	}
}


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

const long long MOD = 1000000007;
const long long INF = 1LL << 60;
const int INT_INF = 1000000000;

int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
// int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[8] = {-1, 0, 1, 1, -1, 1, 0, -1};

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string s;
  ll K;
  cin >> s >> K;
  for (int i = 0; i < s.size(); i++)
  {
    if (s[i] == 'a')
      continue;
    int thre = (int)('z' - '0') - (int)(s[i] - '0');
    thre++;
    cerr << "i: " << i << "   "
         << "thre: " << thre << endl;
    if (K >= thre)
    {
      s[i] = 'a';
      K -= thre;
    }
  }
  if (K >= 0)
  {
    s[s.size() - 1] += K % 26;
  }
  cout << s << endl;
  return 0;
}

// 左からaにすることを試みる　aにできなかったら逆に辞書順では大きくなってしまうのでスキップ　一番右まで行ってしまったらあとは一番右だけ進め続ける．


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

int main(){
 int a;
 string p,s;
 cin >> p >> s ;
 
 p+=p;
 
 a=p.find(s);
 if(a==-1)cout << "No" << endl;
 else cout << "Yes" << endl;
 
 return 0;
}

Measured memory_bytes: 3180
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
	string s;
	cin >> s;
	int cur = -1;
	int prev = s[0]=='e'?1:0;
	int next[] = {7, 3};
	int idx = 0;
	vector<vector<int> > v;
	while(idx < s.size()){
		int x = s[idx] == 'e';
		if(prev != x){
			v[cur].push_back(x);
		}else{
			v.push_back(vector<int>(1, x));
			cur++;
		}
		idx += next[x];
		prev = x;
	}

	reverse(v.begin(), v.end());
	int last = -1;
	bool rest = true;
	idx = 0;
	while(rest){
		rest = false;
		for(int i = 0; i < v.size(); i++){
			if(idx < v[i].size()){
				last = v[i][idx];
				rest = true;
			}
		}
		idx++;
	}

	cout << (last?"egg":"chicken") << endl;

	return 0;
}

Measured memory_bytes: 1240
#include<iostream>
using namespace std;
int main()
{
    long long int H,i,j;
    cin>>H;
    i=1;
    j=2;
    while(1)
    {
        if(H>=i && H<j)
        {
            cout<<j-1<<endl;
            break;
        }
        else
        {
            i=j;
            j=j*2;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define INFL 0x6fffffffffffffffLL
#define MOD 1000000007

int main() {
	ll		a,b,c,d,h,i,j,k,l,m,n,v,w,x,y,z;
	ll		ans = 1;
	
	cin >> n;
	//vector<ll>	aa(n);
	//for(i=0;i<n;i++) cin >> aa[i];
	//vector<ll>	dp(n+1,INFL);
	//vector<vector<ll>>	dp2(x , vector<ll>(y,INFL));

	//if (n>=2) ans = n*(n-1) % MOD;

	ans = 1;
	for(i=1;i<=n;i++) {
		ans = (ans * 10 ) % MOD;
	}
	
	
	b = 1;
	for(i=1;i<=n;i++) {
		b = (b * 9) % MOD;
	}
	b = b * 2 % MOD;

	c = 1;
	for(i=1;i<=n;i++) {
		c = (c * 8) % MOD;
	}
	b = (MOD + b - c) % MOD;

	
	//ans = (MOD + ans + a ) % MOD;
	ans = (MOD + ans - b ) % MOD;
	//ans = (MOD + ans - c ) % MOD;
	

	if (n==1) ans = 0;
	cout << ans << endl;
	return 0;
}


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

#ifdef _DEBUG
#define debug(x) cerr << "line: " << __LINE__ << ", func: " << __func__ << " ->  " << #x << " = " << x << endl
#else
#define debug(x)
#endif

#define all(s) begin(s), end(s)
#define rall(s) rbegin(s), rend(s)
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = ((a)-1); i >= (b); i--)
#define pb push_back
#define sz(a) int((a).size())
#define put(a) ((cout) << (a) << (endl))
#define putf(a, n) ((cout) << (fixed) << (setprecision(n)) << (a) << (endl))
#define deg2rad(x) (((x)*PI) / (180.0))
#define rad2deg(x) (((x) * (180.0)) / PI)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i_i = pair<int, int>;
using ll_ll = pair<ll, ll>;
using d_ll = pair<double, ll>;
using ll_d = pair<ll, double>;
using d_d = pair<double, double>;

static constexpr ll LL_INF = 1LL << 60;
static constexpr int I_INF = 1 << 28;
static constexpr double PI = static_cast<double>(3.14159265358979323846264338327950288);
static constexpr double EPS = numeric_limits<double>::epsilon();

static map<type_index, const char* const> scanType = {
    {typeid(int), "%d"}, {typeid(ll), "%lld"}, {typeid(double), "%lf"}, {typeid(char), "%c"}};

template <class T> static void scan(vector<T>& v);
[[maybe_unused]] static void scan(vector<string>& v, bool isWord = true);
template <class T> static inline bool chmax(T& a, T b);
template <class T> static inline bool chmin(T& a, T b);
template <class T> static inline T gcd(T a, T b);
template <class T> static inline T lcm(T a, T b);
template <class A, size_t N, class T> static void Fill(A (&arr)[N], const T& val);
template <class T> T mod(T a, T m);

int main(int argc, char* argv[]) {
  string S;
  cin >> S;

  int min_change = sz(S) / 2;

  int left = sz(S), right = sz(S);

  rep(i, 0, sz(S) - 1) {
    if (S[i] != S[i + 1]) {
      if (i >= min_change) break;
      left = sz(S) - (i + 1);
    }
  }

  reverse(all(S));
  rep(i, 0, sz(S) - 1) {
    if (S[i] != S[i + 1]) {
      if (i >= min_change) break;
      right = sz(S) - (i + 1);
    }
  }

  put(min(left, right));
  return 0;
}

template <class T> static void scan(vector<T>& v) {
  auto tFormat = scanType[typeid(T)];
  for (T& n : v) {
    scanf(tFormat, &n);
  }
}

static void scan(vector<string>& v, bool isWord) {
  if (isWord) {
    for (auto& n : v) {
      cin >> n;
    }
    return;
  }

  int i = 0, size = v.size();
  string s;
  getline(cin, s);

  if (s.size() != 0) {
    i++;
    v[0] = s;
  }

  for (; i < size; ++i) {
    getline(cin, v[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 T> inline T gcd(T a, T b) { return __gcd(a, b); }

template <class T> inline T lcm(T a, T b) { return (a * b) / gcd(a, b); }

template <class A, size_t N, class T> void Fill(A (&arr)[N], const T& val) {
  std::fill((T*)arr, (T*)(arr + N), val);
}

template <class T> T mod(T a, T m) { return (a % m + m) % m; }


Measured memory_bytes: 512
N, M, X = map(int, input().split())

book = [0] + [list(map(int, input().split())) for _ in range(N)]
ans = N * 10**5 + 1

for i in range(2**N):
    read = [0] * (N+1)
    rikai = [0] * (M+1)
    cost = 0
    for j in range(N):
        read[j+1] = i%2
        i //= 2
    for j in range(1, N+1):
        if read[j] == 1:
            cost += book[j][0]
            for k in range(1, M+1):
                rikai[k] += book[j][k]
    
    if min(rikai[1:]) >= X:
        ans = min(ans, cost)

print(ans if ans != (N * 10**5 + 1) else -1)


Measured memory_bytes: 9228
import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String S = sc.next();
        if (N%2 != 0) {
        		System.out.println("No");
        } else {
        		String t = S.substring(0, N/2);
            String T = S.substring(N/2);
            if (t.equals(T)) {
            		System.out.println("Yes");
            } else {
            		System.out.println("No");
            }
        } 
    }
}

Measured memory_bytes: 21844
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
  let d: u32 = read();
  let t: u32 = read();
  let s: u32 = read();
  
    let ans = if (d > t *s)  { "No" } else { "Yes" };
    println!("{}", ans);
}

Measured memory_bytes: 2128
K = int(input())

def minSunuke(n) :  # n以上の n/S(n) の最小値
    sumDigit = sum(map(int, list(str(n))))
    return n / sumDigit

digit = 0
now = 1

for i in range(K) :
    print(now)
    if minSunuke(now + 10**digit) > minSunuke(now + 10**(digit + 1)) :
        digit += 1
    now += 10**digit


Measured memory_bytes: 3188
import sys
n,m = map(int,raw_input().split())
if n >= m:
    print m//2
    sys.exit(0)
if m > n:
    if m>=(2*n):
        print n + ((m-(2*n))//4)
        sys.exit(0)
    if m < (2*n):
        print m//2
        sys.exit(0)


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

namespace AtCoder.ABC123.A
{
    class Program
    {
        static void Main()
        {
            var sc = new Scanner();
            var points = Enumerable.Range(0, 5).Select(_ => sc.Nextint()).OrderBy(val => val).ToArray();
            var k = sc.Nextint();
            Console.WriteLine(points.Last() - points.First() <= k ? "Yay!" : ":(");
        }
    }

    class Scanner
    {
        string[] s;
        long i;

        char[] cs = new char[] { ' ' };

        public Scanner()
        {
            s = new string[0];
            i = 0;
        }

        public string Next()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return Next();
            i = 0;
            return s[i++];
        }

        public int Nextint()
        {
            return int.Parse(Next());
        }
        public int[] Arrayint(int N, int add = 0)
        {
            int[] Array = new int[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = Nextint() + add;
            }
            return Array;
        }

        public long NextLong()
        {
            return long.Parse(Next());
        }

        public long[] ArrayLong(int N, long add = 0)
        {
            long[] Array = new long[N];
            for (long i = 0; i < N; i++)
            {
                Array[i] = NextLong() + add;
            }
            return Array;
        }

        public double NextDouble()
        {
            return double.Parse(Next());
        }

        public double[] ArrayDouble(long N, double add = 0)
        {
            double[] Array = new double[N];
            for (long i = 0; i < N; i++)
            {
                Array[i] = NextDouble() + add;
            }
            return Array;
        }

        public decimal NextDecimal()
        {
            return decimal.Parse(Next());
        }

        public decimal[] ArrayDecimal(long N, decimal add = 0)
        {
            decimal[] Array = new decimal[N];
            for (long i = 0; i < N; i++)
            {
                Array[i] = NextDecimal();
            }
            return Array;
        }
    }
}


Measured memory_bytes: 13396
N, M = map(int, input().split())
ans = [-1] * N
for _ in range(M):
    i, n = map(int, input().split())
    if (ans[i-1] == -1 or ans[i-1] == n) and not(N > 1 and i == 1 and n == 0):
        ans[i-1] = n
    else:
        print(-1)
        exit()
ans = [n if n != -1 else 0 for n in ans]
if ans[0] == 0 and N > 1:
    ans[0] = 1

print(*ans, sep='')

Measured memory_bytes: 3064
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2
from fractions import gcd
from itertools import permutations, combinations

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

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas



H = intinput()

n = floor(log2(H))

ans = int((1-(2**(n+1)))/(1-2))


# 出力
print(ans)




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

template <class F>
int lower_bound(int i0, int i1, F f) {
    while (i0 != i1) {
        int i = (i0 + i1) / 2;
        if (!f(i)) i0 = i + 1; else i1 = i;
    }
    return i0;
}

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

    int n;
    int64_t a, b;
    cin >> n >> a >> b;

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

    // k��őS���|���邩
    int i = lower_bound(0, 1000000001, [&](int k) {
        int64_t l = k;
        for (int i = 0; i < n; i++) {
            int64_t t = h[i] - b * k;
            if (t <= 0) continue;
            l -= (t + (a - b) - 1) / (a - b);
            if (l < 0) break;
        }
        return l >= 0;
    });

    cout << i << endl;

    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define uniq(v) v.erase(unique(v.begin(),v.end()),v.end())
#define lb(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define ub(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
using Pair = pair<ll,pair<int,int>>;
#define pq priority_queue<Pair, vector<Pair>, greater<Pair>> 
const ll mod=1000000007;
//const ll mod=998244353;
const ld pi=acos(-1.0);
const ll INF = 1LL<<61;
template<class T>bool chmax(T &a, const T &b) { 
  if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) {
  if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる



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

  vector<bool> p(4,false);
  rep(i,4){
    int x;
    cin>>x;
    if(x==1) p[0]=true;
    if(x==4) p[1]=true;
    if(x==7) p[2]=true;
    if(x==9) p[3]=true;
  }

  cout << ((p[0]&&p[1]&&p[2]&&p[3])?"YES":"NO") << endl;

}

Measured memory_bytes: 3608
<?php
  fscanf(STDIN, "%i", $n);
  for ($i = 1; $i <= $n; $i++)
  {
      fscanf(STDIN, "%i %i", $as[$i], $bs[$i]);
  }
  $count = 0;
  for ($i = $n; $i > 0; $i--)
  {
      $count += ($bs[$i] - ($count + $as[$i]) % $bs[$i]) % $bs[$i];
  }
  echo $count.PHP_EOL;
?>


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

  int N , M ;
  cin >> N >> M ;
  if(M<=N*500) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        H = list(map(int, input().split()))

        cnt = 0
        before = H[0]
        ans = 0
        for i in range(1, N):
            if before >= H[i]:
                cnt += 1
                if i == N - 1:
                    ans = max(ans, cnt)
            else:
                ans = max(ans, cnt)
                cnt = 0
            before = H[i]
        print(ans)


if __name__ == '__main__':
    AtCoder().main()

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

struct Node{
    int key;
    Node *parent;
    Node *left;
    Node *right;
};

struct Node *NIL, *root;

void init(){
    root = NIL;
}

void insert(Node* z){
    struct Node* y = NIL; // xの親
    struct Node* x = root;

    while(x != NIL){
        y = x;
        if(z->key < x->key){
            x = x->left;
        }else{
            x = x->right;
        }
    }
    z->parent = y;

    if(y == NIL){
        root = z;
    }
    else if(z->key < y->key){
        y->left = z; 
    }else{
        y->right = z;
    }
}

void print_node_inorder(Node* x){
    if(x == NIL){
        return;
    }
    print_node_inorder(x->left);
    printf(" %d", x->key);
    print_node_inorder(x->right);
}

void print_node_pre(Node* x){
    if(x == NIL){
        return;
    }
    printf(" %d", x->key);
    print_node_pre(x->left);
    print_node_pre(x->right);
}

void print_(){
    print_node_inorder(root);
    printf("\n");
    print_node_pre(root);
    printf("\n");
}

int main(void){
    void init();
    
    int m;
    scanf("%d", &m);

    string com;

    for(int i = 0; i < m; i++){
        cin >> com;
        if(com == "insert"){
            struct Node* n;
            n = (struct Node*)malloc(sizeof(struct Node));
            n->right = NIL;
            n->left = NIL;
            n->parent = NIL;
            scanf("%d", &n->key);
            insert(n);
        }else if(com == "print"){
            print_();
        }else{
            printf("invalid command");
        }
    }

    return 0;
}



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

#define int long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define pb(n) push_back(n);
#define mp make_pair
#define MOD 1000000007
#define INF 9223372036854775807

int n,z;
vector<pair<int,int>> ans;

main() {
    cin >> n;
    z = (n+1)%2;
    rep1(i,n) repo(j,i+1,n+1) if (i^j && i+j ^ n+z) ans.pb(mp(i,j))
    cout << ans.size() << endl;
    rep(i,ans.size()) cout << ans[i].fi << " " << ans[i].se << endl;
}

Measured memory_bytes: 512
object Main {
	def main(args: Array[String]): Unit = {
			val in = new java.util.Scanner(System.in)
			val a = in.nextInt()
			val b = in.nextInt()
		  val c = in.nextInt()
		  val ls = a::b::c::Nil
			val re = ls.sorted
			println(re.apply(0)+" "+re.apply(1)+" "+re.apply(2))

	}
}

Measured memory_bytes: 44964
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
#define Priq priority_queue<int,vi,greater<int>>
#define pb push_back
#define mp make_pair
#define INF (1ll<<62)-1
#define MAX 1000000000
signed main(){
    int N,M; cin>>N>>M;
    vi A(N);
    rep(i,0,N) cin>>A[i];
    vi B(M+1),C(M+1),D(M+1),E(M+1);
    int sum=0,memo=0;
    rep(i,1,N){
        if(A[i]<A[i-1]){
            int X=M-A[i-1];
            sum+=X;
            memo++;
            E[A[i]]++;
            D[A[i]]+=M-A[i-1]+A[i];
            C[A[i-1]]++;
        }
        else{
            C[A[i-1]]++;
            D[A[i]]+=A[i]-A[i-1];
            E[A[i]]++;
        }
    }
    int ans=0;
    REP(i,1,M){
        sum+=memo;
        ans=max(ans,sum-memo);
        memo-=E[i];
        sum-=D[i];
        memo+=C[i];
    }
    ans=-ans;
    rep(i,1,N){
        if(A[i-1]>A[i]) ans+=M-A[i-1]+A[i];
        else ans+=A[i]-A[i-1];
    }
    cout<<ans<<endl;
}



Measured memory_bytes: 4224
from collections import defaultdict
N,T=list(map(int,input().split(" ")))
A=list(map(int,input().split(" ")))
sub=defaultdict(lambda:0)
max1=A[0]
min1=A[0]
for i in range(N):
    if A[i]>=max1>=min1:
        max1=A[i]
        sub[max1-min1]+=1
    elif max1>=A[i]>=min1:
        max1=A[i]
        sub[max1-min1]+=1
    elif min1>=A[i]:
        min1=A[i]
        max1=A[i]
a=list(sub.keys())
b=max(a)
print(sub[b])

Measured memory_bytes: 20960
#include"bits/stdc++.h"


#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iout(x) printf("%d\n",x)
#define lout(x) printf("%lld\n",x)
#define REP(x,l,u) for(int x = (l);x<=(u);x++)
#define RREP(x,l,u) for(int x = (l);x>=(u);x--)
#define mst(x,a) memset(x,a,sizeof(x))
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define se second
#define fi first
#define dbg(x) cout<<#x<<" = "<<(x)<<endl;
#define sz(x) ((int)x.size())
#define cl(x) x.clear()

typedef  long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
using namespace std;

const int maxn = 200010;
const int mod = 1e9+7;
const int MAX = 1000000010;
const double eps = 1e-6;
const double PI = acos(-1);

template<typename T> inline void read(T &x){
x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;
}

template<typename A,typename B> inline void read(A&x,B&y){read(x);read(y);}
template<typename A,typename B,typename C> inline void read(A&x,B&y,C&z){read(x);read(y);read(z);}
template<typename A,typename B,typename C,typename D> inline void read(A&x,B&y,C&z,D&w){read(x);read(y);read(z);read(w);}
template<typename A,typename B> inline A fexp(A x,B p){A ans=1;for(;p;p>>=1,x=1LL*x*x%mod)if(p&1)ans=1LL*ans*x%mod;return ans;}
template<typename A,typename B> inline A fexp(A x,B p,A mo){A ans=1;for(;p;p>>=1,x=1LL*x*x%mo)if(p&1)ans=1LL*ans*x%mo;return ans;}

int n,sm;

int A[maxn];

bitset<2001*2000> dp;

int main(){
	read(n);
	REP(i,1,n)read(A[i]),sm+=A[i];
	dp[0]=1;
	REP(i,1,n)dp|=dp<<A[i];
	sm=(sm+1)>>1;
	REP(i,sm,sm*2+1)if(dp[i]){iout(i);return 0;}
	return 0;
}


Measured memory_bytes: 1664
#include <stdio.h>

int main(void) {
	int d_num,now_d;
	int n;
	int height[100];
	int i;
	int u_max,d_max;
	int now;
	scanf("%d",&d_num);
	for(now_d=0;now_d<d_num;now_d++) {
		scanf("%d",&n);
		for(i=0;i<n;i++)scanf("%d",&height[i]);
		u_max=d_max=0;
		for(i=1;i<n;i++) {
			if(height[i]>height[i-1]) {
				now=height[i]-height[i-1];
				if(now>u_max)u_max=now;
			} else {
				now=height[i-1]-height[i];
				if(now>d_max)d_max=now;
			}
		}
		printf("%d %d\n",u_max,d_max);
	}
	return 0;
}

Measured memory_bytes: 0
from itertools import product

n = int(input())
l1 = []
for _ in range(n):
    l2 = []
    for _ in range(int(input())):
        l2.append(list(map(int, input().split())))
    l1.append(l2)

ans = 0
for k in product([1, 0], repeat=n):
    ng_check = False
    for i, j in enumerate(l1):
        if k[i] == 0:  # 不親切な人とした場合は弾く
            continue
        for x in j:  # 整合性が取れてるかチェック
            if k[x[0] - 1] != x[1]:
                ng_check = True  # 不整合
                break
        if ng_check:  # 整合性が取れてない場合
            break
    else:
        ans = max(ans, sum(k))
print(ans)

Measured memory_bytes: 9220
#include<bits/stdc++.h>
#define maxn ((int)1e5)
using namespace std;
int n;
long long a[maxn],res=0;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	for(int i=0;i<n;i++)
	{
		res+=a[i]/2;
		a[i]%=2;
		if(a[i]&&a[i+1])
		{
			++res;
			--a[i];
			--a[i+1]; 
		}
	}
	cout<<res<<endl;
	return 0;
}

Measured memory_bytes: 1024
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main implements Runnable {

	public static void main(String[] args) {

		new Thread(null, new Main(), "", 16 * 1024 * 1024).start();

	}

	@Override
	public void run() {
		exec();
	}

	private void exec() {

		FastScanner sc = new FastScanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();

		if(a <= 9 && a >= 1 && b <= 9 && b >= 1) {
			System.out.println(a * b);
		} else {
			System.out.println(-1);
		}

	}

}

class FastScanner {

	private final InputStream in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	public FastScanner(InputStream in) {
		this.in = in;
	}

	private boolean hasNextByte() {
		if(ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if(buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if(hasNextByte()) {
			return buffer[ptr++];
		} else {
			return -1;
		}
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	public boolean hasNext() {
		while(hasNextByte() && !isPrintableChar(buffer[ptr])) {
			ptr++;
		}
		return hasNextByte();
	}

	public String next() {
		if (!hasNext()) throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while(isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			}else if(b == -1 || !isPrintableChar(b)){
				return minus ? -n : n;
			}else{
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
		return (int) nl;
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}

}


Measured memory_bytes: 23124
#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;

double dis(int x1,int y1,int x2,int y2)
{
	double temp=(double)sqrt(pow((x1-x2),2)+pow((y1-y2),2));
	return temp;
}

int fact(int n)
{
	return(n==1||n==0) ? 1 : fact(n-1)*n;
}

int main()
{
	int N,i,j,x[10000],y[10000],nc2,pair;
	double m,n,s[1000][1000];
	while(cin>>N)
	{
		for(i=0;i<N;i++)
		{
			cin>>x[i]>>y[i];
		}
		nc2=(fact(N))/(2*fact(N-2));
		pair=(fact(N)*(N-1))/nc2;
		
		cout<<showpoint;
		cout<<fixed;
		cout<<setprecision(10);
	
		for(i=0,j=1,m=0,n=0;j<N&&i<N;j++)
		{
			if(i>=j){
				continue;
			}
			s[i][j]=dis(x[j],y[j],x[i],y[i]);
		    m=s[i][j]*pair;
		    n=n+m;	
			if(j==N-1){
				j=-1;
				i++;
			}
		}	
		cout<<n/fact(N);
	}
}

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

int main(){
    int n;
    cin >> n;
    int A[n] = {};
    for(int i = 0; i < n-1; i++){
        int x;
        cin >> x;
        A[x-1] += 1;
    }
    for(int i = 0; i < n; i++){
        cout << A[i] << endl;
    }

    return 0;
}



Measured memory_bytes: 4416