akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include<string.h>
 
typedef long long int ll;
#define all(x) (x).begin(), (x).end()
 
using namespace std;

int nxt() {
    int x;
    cin >> x;
    return x;
}

ll nxtl(){
    ll x;
    cin>>x;
    return x;
}
 
void SieveOfEratosthenes(int n,vector <int> &primes) 
{ 
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          primes.push_back(p);
} 
 
ll max(ll a,ll b)
{
    if(a>b)
        return a;
    return b;
}
 
ll power(ll x, ll y,ll mod) 
{ 
    ll temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2,mod); 
    if (y%2 == 0) 
        return (temp*temp)%mod; 
    else
        return (((x*temp)%mod)*temp)%mod; 
} 
void cal(vector <bool> &visited,ll cur,ll &n,ll &sum);
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n=nxtl();
    vector <pair<ll,ll> > v(n);
    for(int i=0;i<n;i++)
        cin>>v[i].first>>v[i].second;
    ll den=1;
    for(int i=1;i<=n;i++)
        den*=i;
    ll mul=1;
    for(int i=1;i<=n-1;i++)
        mul*=i;
    mul*=2;
    double fin=mul;
    double sum=0;
    //cout<<"mul: "<<mul<<endl;
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
            sum+=(fin*(sqrt(pow(v[i].first-v[j].first,2)+pow(v[i].second-v[j].second,2))));
    sum/=den;
    cout<<setprecision(10)<<sum<<endl;

    return 0;   
}

void cal(vector <bool> &visited,ll cur,ll &n,ll &sum,ll partial)
{
    if(cur==n)
    {
        sum+=partial;
    }
    else
    {

    }
}


 
 


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <tuple>
#include <cmath>
using namespace std;

int main(int argc, const char * argv[]) {
  int d,n;
  cin >> d >> n;
  int64_t step = pow(100,d);
  int64_t i = step;
  int64_t cnt = 0;
  
  while(true){
    if(d == 0 && i % 100 != 0){
      cnt++;
    }else if(d == 1 && (i / 100) % 100 != 0){
      cnt++;
    }else if(d == 2 && (i / 10000) % 100 != 0){
      cnt++;
    }
    if(cnt == n ){
      cout << i << endl;
      return 0;
    }
    i+=step;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define R register
#define ll long long
#define mp make_pair
#define pii pair<int, int>
using namespace std;
const int N = 610;

int n, m, g[N][N], d[N], to[N];
double f[N];

template <class T>
inline void read(T &x) {
    x = 0;
    char ch = getchar(), w = 0;
    while (!isdigit(ch)) w = ch == '-', ch = getchar();
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    x = w ? -x : x;
    return;
}

int main() {
    int x, y;
    read(n), read(m);
    for (R int i = 1; i <= m; ++i)
        read(x), read(y), g[x][y] = 1, ++d[x];
    for (R int i = n - 1; i; --i) {
        for (R int j = i + 1; j <= n; ++j)
            if (g[i][j])
                f[i] += f[j], to[i] = f[j] > f[to[i]] ? j : to[i];
        ++(f[i] /= d[i]);
    }
    double ans = f[1];
    for (R int i = n - 1; i; --i) {
        if (d[i] == 1) continue;
        for (R int j = n - 1; j; --j) {
            f[j] = 0;
            for (R int k = j + 1; k <= n; ++k) {
                if (!g[j][k] || (j == i && k == to[i])) continue;
                f[j] += f[k];
            }
            ++(f[j] /= d[j] - (i == j));
        }
        ans = min(ans, f[1]);
    }
    printf("%.10lf\n", ans);
    return 0;
}

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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a*b/gcd(a, b);
}

int main()
{
    cout << fixed << setprecision(15);
    ll a, b, c, d;
    cin >> a >> b >> c >> d;

    if(abs(a-c) <= d){
        cout << "Yes" << endl;
        return 0;
    }
    if((abs(a-b) <= d) && (abs(b-c) <= d)){
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl;
    return 0;
}

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

#define fi first
#define se second
#define be begin
#define en end
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ALL(a) (a).be() , (a).en()
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)        //repeat n times
#define REP2(i,s,n) for(int (i)=(s);(i)<(n);(i)++)   //repeat from s to n 
#define REPD(i,n) for(int (i)=(n);(i)>=0;(i)--)      //repeat from n to 0
#define REPD2(i,s,e) for(int (i)=(s);(i)>=(e);(i)--) //repeat from s to e
#define RANGE(i,v) for(auto &(i):v)                  //repeat range
#define ASIZE(a) (sizeof(a) / sizeof(a[0]))          //array size

using LL = long long;

template<typename T> using V = vector< T >;
using Vi = V<int>;
using Vll = V<LL>;
using Vs = V<string>;

int main(){
    int n;
    cin>>n;
    Vi p(n);
    REP(i,n) cin>>p[i];
    Vi q = p;
    sort(ALL(q));
    
    int cnt = 0;
    REP(i,n){
        if(p[i]!=q[i]) cnt++;
    }

    if(cnt>2){
        cout<<"NO"<<endl;
    }else{
        cout<<"YES"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
n, p = list(map(int, input().split()))
# a = list(map(int, input().split()))
s = input()
rem = [0 for i in range(p)]
total = 0
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
    print(ans)
else:
    for i in range(len(s)-1, -1, -1):
        total += int(s[i])*pow(10, len(s)-i-1, p)
        total %= p
        if total % p == 0:
            ans += 1
        ans += rem[total]
        rem[total] += 1

    print(ans)


Measured memory_bytes: 3500
#include<iostream>
#include<string>
#include<algorithm>    
#include<cmath>
#include<map>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<stack>
#include<queue>
#include<tuple>
#include<cassert>
#include<set>
#include<functional>
//#include<bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define rep(i, x) for(ll i = 0; i < x; i++)
#define rep2(i, x) for(ll i = 1; i <= x; i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
const ll INF = 1000000000000000000;
const ll mod = 1000000007;
const ll MOD = 998244353;
const ld pi = 3.141592653589793238;

bool isprime(int p) {
	if (p == 1) return false;
	for (int i = 2; i < p; i++) {
		if (p % i == 0) return false;
	}
	return true;
}
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (a % b == 0)return b;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}
ll keta(ll n) {
	ll res = 0;
	while (n >= 1) {
		res += n % 10; n /= 10;
	}
	return res;
}
ll modpow(ll x, ll y) {
	ll res = 1;
	while (y) {
		if (y % 2) { res *= x; res %= mod; }
		x = x * x % mod; y /= 2;
	}
	return res;
}
ll nCk(ll n, ll k) {
	ll a = 1, b = 1;
	for (int h = n - k + 1; h <= n; h++) { a *= h; a %= mod; }
	for (int h = 1; h <= k; h++) { b *= h; b %= mod; }
	return a * modpow(b, mod - 2) % mod;
}
//printf("%.10f\n", n);


signed main() {
	ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	string s, t;
	ll n, x, m, cnt = 0, ans = 0, first = 0, rupe = 0, ac = 0;
	cin >> n >> x >> m;
	map<ll, ll> test, rui, ok;//okは場所
	ans += x; test[1] = x; rui[1] = x; ok[x] = 1;
	for (int h = 2; h <= n; h++) {
		test[h] = (test[h - 1] * test[h - 1]) % m;
		if (ok[test[h]] == 0) { rui[h] = test[h] + rui[h - 1]; ok[test[h]] = h; }
		else {
			cnt = rui[h - 1] - rui[ok[test[h]] - 1]; rupe = h - ok[test[h]];
			ans = rui[ok[test[h]]]; first = ok[test[h]]; ac = ok[test[h]]; break;
		}
		if (h == n) { cout << rui[n] << endl; return 0; }
	}
	ll sum = 0;
	if (rupe == 0) { cout << ans << endl; return 0; }
	while (true) {
		if (first + rupe <= n) {
			ll yuu = (n - first) / rupe;
			ans += yuu * cnt; first += rupe * yuu;
		}
		else { ans += test[ac + sum + 1]; sum++; first++; }
		if (first == n) { break; }
		//ans %= m;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 12944
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
long long a[1000005];
int main()
{
    int n,x=1,count=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
      scanf("%d",&a[i]);
    sort(a,a+n);
    for(int i=1;i<n;i++)
    {
        if(a[i]==a[i-1])
          x=(x+1)%2;
        else
        {
            count+=x;
            x=1;
        }
    }
    if(x%2)
      count++;
    printf("%d\n",count);
    return 0;
}

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



// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    string s;
    cin >> s;
    int n = s.length();
    rep(i,n)
    {
        if (s[i]=='?')
        {
            // ここから数を数える
            int idx = i;
            while(idx < n)
            {
                if (s[idx] == '?') idx++;
                else break;
            }
            int hatena_sz = idx - i;
            
            // ここから書き込み
            // cout << hatena_sz << endl;
            bool flag;
            flag = false;
            if (i!=0 && s[i-1]=='P') flag = true;

            for(;i<idx;i++)
            {
                if (idx-i==1)
                {
                    s[i] = 'D';
                    break;
                }

                if (flag)
                {
                    s[i] = 'D';
                }
                else
                {
                    s[i] = 'P';
                }
                flag = !flag;
            }
            // cout << s << endl;
        }
    }
    cout << s << endl;
}


Measured memory_bytes: 3752
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<utility>
using namespace std;

int main(){
    
    long long n,m;
    cin >> n >> m;
    long long mod = 1000000007;
    vector<long long> dp(n+2,0);
    for (int i = 0; i < m; i++)
    {
        int tmp;
        cin >> tmp;
        dp[tmp] = -1;
    }
    
    dp[n] = 1;

    for (int i = n-1; i>=0; i--)
    {
        if(dp[i] == -1){
          dp[i] = 0;
        }else{
          dp[i] = dp[i+1] + dp[i+2];
          dp[i] = dp[i]%mod;
        }
    }

    cout << dp[0] << endl;
}

Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<sstream>
#include<stack>
#include<cmath>
#include<vector>
#include<iomanip>
#include<map>
#include<set>
#include<queue>
#include<deque>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,n) for(int i = 0; i < n;i++)
#define ALL(a)  (a).begin(),(a).end()
#define fix  fixed << setprecision(10)
const int MOD = 1000000007;
const ll INF = (1LL << 60);
string s; ll n, m, k, q = 0, ans, sum =INF; 
int main() {
    cin >> s;
    rep(i, 3) {
        if (s[i] == '7') {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}


Measured memory_bytes: 3584
//https://atcoder.jp/contests/abc148/tasks/abc148_a
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll a1;
	cin>>a1;
	ll a2;
	cin>>a2;
	ll a3;
	cin>>a3;
	if(a1+a2+a3>=22)
	{
		cout<<"bust"<<"\n";
	}
	else
	{
		cout<<"win"<<"\n";
	}
	return 0;
}

Measured memory_bytes: 3640
package main

import (
  "fmt"
  "strconv"
)

func main() {
  var a, b string
  fmt.Scan(&a, &b)

  j, _ := strconv.Atoi(b)

  aNum := a
  for i := 1; i < j; i++ {
    a += aNum
  }

  bNum := b
  k, _ := strconv.Atoi(aNum)
  for i := 1; i < k; i++ {
    b += bNum
  }

  if a > b {
    fmt.Println(b)
  } else {
    fmt.Println(a)
  }
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
//typedef tree <int,null_type,less <int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#define rep(g, i, n) for (ll g = i; g < n; g++)
#define rev(g, n, i) for (ll g = n - 1; g >= i; g--)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(v) v.begin(), v.end()
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define um unordered_multiset
#define us unordered_set
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define ve vector
#define cc continue
#define bb break
#define rem 1000000007
#define debug(n1) cout<<"debug... "<<n1<<"\n"
#define PI 3.141592653589793238462643383279502
//fflush(stdin);
// do {
// // process permutation
// } while (next_permutation(permutation.begin(),permutation.end()));
class abc
{
    public:
    ll x,y;
};
int main()
{
    FAST
    // freopen("input1.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    /*ll tests;
    cin>>tests;
    rep (gg,0,tests)
    {}*/
    ll n;
    cin>>n;
    map <string,ll> m1;
    ve <pair<string,ll>> v1(n);
    ve <ll> ps(n);
    rep (i,0,n)
    {
        cin>>v1[i].first>>v1[i].second;
        m1[v1[i].first]=i;
    }
    ps[0]=v1[0].second;
    rep (i,1,n)
    {
        ps[i]=v1[i].second+ps[i-1];
    }
    string s;
    cin>>s;
    cout<<ps[n-1]-ps[m1[s]]<<"\n";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define eps 1e-8

int A,B,C,D,E,F;
int dp[3005];

int main()
{
    int sb = scanf("%d%d%d%d%d%d",&A,&B,&C,&D,&E,&F);
    if (sb==0) return 0;
    memset(dp,0,sizeof(dp));
    dp[0]=1;
    for (int k=C;k<=F;k++)
        if (dp[k-C]) dp[k]=1;
    for (int k=D;k<=F;k++)
        if (dp[k-D]) dp[k]=1;

    int sum=0,sugar=0;
    for (int i=0;i<=100;i++)
    {
        for (int j=0;j<=100;j++)
        {
            if (i==0&&j==0) continue;
            int wat = 100*(i*A+j*B);
            if (wat>=F) break;

            int x = (i*A+j*B)*E;
            x=min(x,3000);

            for (int k=0;k<=F-wat;k++)
            {
                if (k>x) break;
                if (dp[k])
                {
                    if (k*sum>sugar*(wat+k)||sum==0)
                    {
                        sum=(k+wat);
                        sugar=k;
                    }
                }
            }
        }
    }
    printf("%d %d\n",sum,sugar);
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<cstdio>
#include<queue>
#include<deque>
#include<map>
#include<stack>
#include<set>
#include<utility>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
const int MAXN=100000;
const int MAXE=100000;
const int MAXV=10000;
const ll INF=(1LL<<31)-1;
const ll MOD=1e9+7;

struct segtree{
    vector<ll> dat;
    ll size;
    segtree(int n):dat(2*n-1,INF),size(n){};
    void update(int i,ll x){
        i+=this->size-1;
        dat[i]=x;
        while(i>0){
            i=(i-1)/2;
            dat[i]=min(dat[i*2+1],dat[i*2+2]);
        }
    }
    ll find(int s,int t){
        return query(s,t+1,0,0,this->size);
    }
    ll query(int a,int b,int k,int l,int r){
        if(r<=a||b<=l) return INF;
        else if(a<=l&&r<=b) return dat[k];
        else{
            ll v1=query(a,b,k*2+1,l,(l+r)/2);
            ll v2=query(a,b,k*2+2,(l+r)/2,r);
            return min(v1,v2);
        }
    }
};
int main(){
    int n,q;cin>>n>>q;
    int N=1;
    while(N<n) N*=2;
    segtree st(N);
    while(q--){
        ll com,x,y;
        cin>>com>>x>>y;
        if(com==0) st.update(x,y);
        else cout<<st.find(x,y)<<endl;
    }
    return 0;
}


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

int main(){
	int number, items, sum = 0,temp;
	cin >> number >> items;
	vector<int> v;
	for(int i =0;i<number;i++){
		cin >> temp;
		v.push_back(temp);
	}
	sort(v.begin(),v.end());
	for(int i = 0; i<items;i++)
		sum += v[i];
	cout << sum;
}


Measured memory_bytes: 3628
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define PB emplace_back
#define ALL(x) (x).begin(),(x).end()
#define endl '\n'

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using pi = pair<int,int>;
using pll = pair<ll,ll>;

constexpr int IN = 1000005;
constexpr int INF = 1e9+5;
constexpr int INI = -1;


int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tab [33] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int k;
    cin >> k;
    cout << tab[k-1];

    return 0;
}


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

a = []  # Map

for i in range(H):
    a.append(input())

res  =  [ [0]*W for i in range(H)]

mx = [-1, -1, -1, 1, 1, 1, 0, 0]  # x direction
my = [-1, 0, 1, -1, 0, 1, -1, 1]  # y direction

for h in range(H):
    for w in range(W):
        cnt = 0  # bomb cnt
        if a[h][w] == '#':
            res[h][w] = '#'
        else:
            for i in range(len(mx)):  # move x
                    x = h + mx[i]
                    y = w + my[i]
                    if (0 <= x <= H-1) and (0 <= y <= W-1):
                        if a[x][y] == '#':
                            cnt += 1
            res[h][w] = cnt


for i in range(H):
    for j in range(W):
        print("{}".format(res[i][j]),end="")
    print()


Measured memory_bytes: 9264
#include "bits/stdc++.h"
using namespace std;
/////////////////// TYPES & MACROS ///////////////////////////////
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define vv vector
#define exist(s,e) (s.find(e)!=s.end())
#define sz(x) ((int)(x).size())
#define int ll
typedef long long ll; typedef long double ld; typedef double dd;typedef vector<int> vi; typedef pair<int, int> pii;typedef pair<ll,ll> pll;
ll INFLL=(ll)4e18, MOD=1e9+7; const int INF=0x3f6f6f6f;
//////////////////// DEBUG /////////////////////////////////////////
#define D(x) cerr<<#x<<" is:\t"<<x<<'\n';
#define DD(x,y) cerr<<'('<<#x<<','<<#y<<") are:\t"<<x<<' '<<y<<'\n';
#define DDD(x,y,z) cerr<<'('<<#x<<','<<#y<<','<<#z<<") are:\t"<<x<<' '<<y<<' '<<z<<'\n';
/////////////////// VARIABLES & FUNCTIONS//////////////////////////
vv<vv<int>> adj; vi vis, color, level; int dx8[]={0,1,1,1,0,-1,-1,-1}, dy8[]={1,1,0,-1,-1,-1,0,1},dx4[]={0,1,0,-1}, dy4[]={1,0,-1,0};
inline ll mexp(ll x,ll n,ll m=MOD){ll res=1;x%=m;while(n){if(n&1)res=(res*x)%m;n>>=1;x=(x*x)%m;}return res;}
inline ll gcd(ll a, ll b){while (a>0 && b>0){if(a>b)a%=b;else b%=a;}return a+b;}



///////////////////// MAIN STARTS //////////////////////////////////
int32_t main(void){
ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
cout<<fixed;cerr<<fixed; cout<<setprecision(1); cerr<<setprecision(3);
mt19937 genr(chrono::high_resolution_clock::now().time_since_epoch().count());


ll n,k; cin>>n>>k;
vv<ll> h(n), dp(n+1,INFLL);
for(int i=0;i<n;++i) cin>>h[i];
dp[1]=0;
dp[2]=abs(h[0]-h[1]);
for(int i=3;i<=n;++i){
	for(int j=1;j<=k && i-j>0;++j) dp[i]=min(dp[i], dp[i-j]+abs(h[i-1]-h[i-j-1]));
}
//for(auto& e: dp) cerr<<e<<' '; cerr<<'\n';
cout<< dp[n] <<'\n';

return 0;
}


Measured memory_bytes: 1792
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>


int main(){

 long long int N,M;
  scanf("%lld %lld",&N,&M);

/*
  char A[];
  scanf("%s",A);
  */

  long long int A[N+1];
  long long int x;
  int i,j;
  for (i=1;i<=N;i++){
    A[i]=0;
  }
 long long int d[M+1];
 for(i=1;i<=M;i++){
  scanf("%lld",&d[i]);
  for(j=0;j<d[i];j++){
   scanf("%lld",&x);
   A[x] = 1;
   }
 }
  int counter;
  counter =0;
  for (i=1;i<=N;i++){
    if(A[i]==0){
      counter+=1;
    }
  }
  printf("%d",counter);







 return(0);
 }


Measured memory_bytes: 1732
#include<stdio.h>
	#include<string.h>
	
	char aki[10]={"AKIHABARA"};
	
	int main(){
		char s[51];
		scanf("%s",s);
		int len=strlen(s);
		int x=0;
		int test=0;
		int count=0;
		int y=0;
		int found=0;
		int j=0;
		for(int i=0;i<len;i++){
			if(s[i]=='A'){
				count++;
			}else if(s[i]=='K'||s[i]=='I'||s[i]=='H'||s[i]=='B'||s[i]=='R') y++;
			if(count>4||y>5){
				test=1;
				break;
			}
			found=0;
			while(j<9){
				if(s[i]==aki[j]){
					found=1;
	//				if(j!=0&&aki[j-1]!='A'&&aki[j-1]!='0'){
	//					test=1;
	//					break;
	//				}else{
	//					aki[j]='0';
	//					break;
	//				}
					int temp=j-1;
					int ct=0;
					while(temp>=0){
						if(aki[temp]!='0'&&aki[temp]!='A'){
							test=1;
							break;
						}
						temp--;
					}
					if(test==1) break;
					else{
//						if(aki[j+1]=='0'){
//							test=1;
//							break;
//						}
						aki[j]='0';
						break;
					}
				}
				j++;
			}
			if(found==0){
				test=1;
				break;
			}
			if(test==1){
				break;
			}
		}
		if(y!=5) test=1;
//		printf("%s %d\n",aki,y);
		if(test==1) printf("NO\n");
		else printf("YES\n");
		return 0;
	}

Measured memory_bytes: 128
import java.io.*;
import java.util.*;
public class Main
{
	String s;
	int n;
	boolean visited[];
	int finalpos[],walk[];
	private void solve()throws IOException
	{
		s=nextLine();
		n=s.length();
		visited=new boolean[n+1];
		finalpos=new int[n+1];
		walk=new int[n+1];
		for(int i=1;i<=n;i++)
			if(visited[i]==false)
				dfs(i);
		int count[]=new int[n+1];
		for(int i=1;i<=n;i++)
			count[finalpos[i]]++;
		for(int i=1;i<=n;i++)
			out.print(count[i]+" ");
		out.println();
	}
	void dfs(int v)
	{
		visited[v]=true;
		if(s.charAt(v-1)=='L')
		{
			if(s.charAt(v-2)=='R')
			{
				walk[v]=0;
				finalpos[v]=v;
				if(visited[v-1]==false)
					dfs(v-1);
			}
			else
			{
				if(visited[v-1]==false)
					dfs(v-1);
				walk[v]=1+walk[v-1];
				if(walk[v]%2==0)
					finalpos[v]=finalpos[v-walk[v]];
				else
					finalpos[v]=finalpos[v-walk[v]]-1;
			}
		}
		else
		{
			if(s.charAt(v)=='L')
			{
				walk[v]=0;
				finalpos[v]=v;
				if(visited[v+1]==false)
					dfs(v+1);
			}
			else
			{
				if(visited[v+1]==false)
					dfs(v+1);
				walk[v]=1+walk[v+1];
				if(walk[v]%2==0)
					finalpos[v]=finalpos[v+walk[v]];
				else
					finalpos[v]=finalpos[v+walk[v]]+1;
			}
		}
	}

	 
	///////////////////////////////////////////////////////////

	public void run()throws IOException
	{
		br=new BufferedReader(new InputStreamReader(System.in));
		st=null;
		out=new PrintWriter(System.out);

		solve();
		
		br.close();
		out.close();
	}
	public static void main(String args[])throws IOException{
		new Main().run();
	}
	BufferedReader br;
	StringTokenizer st;
	PrintWriter out;
	String nextToken()throws IOException{
		while(st==null || !st.hasMoreTokens())
		st=new StringTokenizer(br.readLine());
		return st.nextToken();
	}
	String nextLine()throws IOException{
		return br.readLine();
	}
	int nextInt()throws IOException{
		return Integer.parseInt(nextToken());
	}
	long nextLong()throws IOException{
		return Long.parseLong(nextToken());
	}
	double nextDouble()throws IOException{
		return Double.parseDouble(nextToken());
	}
}

Measured memory_bytes: 50260
N = int(input())

W = map(int, input().split())

Wli = list(W)

sub = 10000000000000

for i in range(1,N):
    a = 0
    b = 0
    for j in range(0,i):
        a += Wli[j]
    for k in range(i,len(Wli)):
        b += Wli[k]

    if abs(a-b) < sub:
        sub = abs(a-b)

print(sub)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
#define FIO                ios_base::sync_with_stdio(false);cin.tie(NULL);
vector<ll>g[100005];
vector<ll>dp(100000,-1);

ll dfs(ll n)
{
    if(dp[n]!=-1)
        return dp[n];
    ll ans=0;
    for(auto k:g[n])
    {
        ans=max(ans,dfs(k)+1);
    }
    return dp[n]=ans;
}

int main()
{
    FIO;
    ll n,m;
    cin>>n>>m;
    for(ll i=0;i<m;i++)
    {
        ll x,y;
        cin>>x>>y;
        x--;
        y--;
        g[x].push_back(y);
    }
    ll ret=0;
    for(ll i=0;i<n;i++)
    {
        ret=max(ret,dfs(i));
    }
    cout<<ret<<endl;
    return 0;
    
}

Measured memory_bytes: 11508
#include<bits/stdc++.h>
using namespace std;
int main() {
 vector<char> s(100);
   for(int i=0; i<s.size(); i++) cin >> s.at(i);
  if(s.at(0) == s.at(1) && s.at(1) == s.at(2))
   cout << "No" << endl; 
  else  cout << "Yes" << endl; 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[100009];
int main()
{

    int n, m;
    cin >> n >> m;
    int sum = 0;
    for(int i =0; i<n; i++)
    {
        cin >> a[i];
        sum+=a[i];
    }
    int x  = sum/(4*m);
    if(1.0*sum/(4*m) > x)
        x++;
    for(int i=0;i <n; i++)
    {
        if(a[i] >= x)
            m--;
    }
    if(m>0)
        cout << "No";
    else
        cout << "Yes";
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main(){
    string S;
    cin >> S;
    
    int ans = 700;
    if(S[0] == 'o'){
        ans += 100;
    }
    if(S[1] == 'o'){
        ans += 100;
    }
    if(S[2] == 'o'){
        ans += 100;
    }
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import sys
n = input()
count = 0
Ss = []
Hs = []
Cs = []
Ds = []
while count<n:
    mark, num = raw_input().split()
    #num = int(num)
    if mark == 'S':
        Ss.append(num)
    elif mark == 'H':
        Hs.append(num)
    elif mark == 'C':
        Cs.append(num)
    elif mark == 'D':
        Ds.append(num)
    else :
        print "error"
        sys.exit()
    count+=1
for x in xrange(1,14):
    if str(x) not in Ss:
        print "S "+str(x)
for x in xrange(1,14):
    if str(x) not in Hs:
        print "H "+str(x)
for x in xrange(1,14):
    if str(x) not in Cs:
        print "C "+str(x)
for x in xrange(1,14):
    if str(x) not in Ds:
        print "D "+str(x)

Measured memory_bytes: 6464
#include<bits/stdc++.h>
#include<climits>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int              long long
#define umapii           unordered_map<int,int>
#define pqmaxi           priority_queue<int>
#define pqmini           priority_queue<int,vector<int>,greater<int>>
#define arr(type,a,n)    type* a = new type[n];
#define ff               first
#define ss               second
#define pb               push_back
#define w(t)             int t;cin>>t;while(t--)
#define popb             pop_back
#define mod              pow(10,9)+7;
#define mapii            map<int,int>
#define mp               make_pair
#define vint             vector<int>
#define presesion        fixed<<presesion(y)<<x
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>pbds;
int32_t main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output2.txt", "w", stdout);
#endif

	int n, t;
	cin >> n >> t;
	int a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int count = t;
	for (int i = 1; i < n; i++) {
		if (a[i] - a[i - 1] < t) {
			count += a[i] - a[i - 1];
		} else {
			count += t;
		}
	}
	cout << count << endl;

}

Measured memory_bytes: 5168
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#define pb push_back
#define all(c) c.begin(),c.end()
#define MOD 998244353
typedef double ld;
#define PI 3.14159265

int pSum[90001];

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

    int h , w , d;
    cin >> h >> w >> d;
    int v;
    map<int , PII> mp;
    for(int i = 1 ; i <= h ; i++) {
        for(int j = 1 ; j <= w ; j++) {
            cin >> v;
            mp[v] = {i , j};
        }
    }

    for(int i = d + 1 ; i <= w * h ; i++) {
        pSum[i] = (pSum[i - d] + abs(mp[i].first - mp[i - d].first) + abs(mp[i].second - mp[i - d].second));
    }

    int q;
    cin >> q;
    int l , r;
    for(int i = 0 ; i < q ; i++) {
        cin >> l >> r;
        cout << pSum[r] - pSum[l] << endl;
    }

    return 0;
}


Measured memory_bytes: 7168
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define zero_pad(num) setfill('0') << std::right << setw(num)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;

int main() {
    vector<string> s(3);
    rep(i, 3) cin >> s[i];
    rep(i, 3) cout << s[i][i];
    cout << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N =sc.nextInt();
		int[] n =new int[N];
		for(int i=0;i<N;i++) {
			n[i]=sc.nextInt();
		}
		
		int m =0;
		int i=0;
		while(i<N) {
			
			if(n[i]%2==0) {
				n[i]=n[i]/2;
				m++;
			}else {
				i++;
			}
		}
		
		
		System.out.println(m);
	}
}

Measured memory_bytes: 35548
#include<iostream>
#include<algorithm>
using namespace std;
long long a,b,c;
int main()
{
	cin>>a>>b>>c;
   for(int i=1;i<=999;i++)
   {
   	if((a*i)%b==c)
   	{
   		cout<<"YES"<<endl;
   		return 0;
   	}
   }
   cout<<"NO"<<endl;
   return 0;
}

Measured memory_bytes: 256
l =list(int(input()) for i in range(5))
a =[]
time = 0
for i in range(5):
  if l[i]%10!=0:
    a.append(l[i]%10)
  else:
    a.append(9)
#print(a)
b = a.index(min(a))
#print(b)
for i in range(5):
  time += (-(-l[i]//10))*10
  #print(time)
time -= (-(-l[b]//10)*10) - l[b]
print(time)


Measured memory_bytes: 3064
import java.util.Scanner;

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

        int min = 200001;
        int count = 0;
        for (int i = 0; i < n; i++) {
            final int p = scanner.nextInt();
            if (p <= min) {
                count++;
                min = p;
            }
        }

        System.out.println(count);
    }
}


Measured memory_bytes: 62488
l = [0 for _ in range(64)]

for i in range(int(input())):
    query = list(input().split())
    order = query[0]
    if order == "0":
        print(1 if l[int(query[1])] else 0)
    elif order == "1":
        l[int(query[1])] = 1
    elif order == "2":
        l[int(query[1])] = 0
    elif order == "3":
        l[int(query[1])] ^= 1
    elif order == "4":
        print(1 if all(l) else 0)
    elif order == "5":
        print(1 if any(l) else 0)
    elif order == "6":
        print(1 if not any(l) else 0)
    elif order == "7":
        print(sum(l))
    elif order == "8":
        tmp = 0
        for i in reversed(range(64)):
            tmp += l[i] * 2**i
        print(tmp)
    ##print(l[:10])



Measured memory_bytes: 5624
#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int> vec;
	for(int i(0); i < 2 * n; i++) {
		int x;
		cin >> x;
		vec.push_back(x);
	}
	int ans(0);
	sort(vec.begin(), vec.end());
	for(int i(0); i + 1 < (int)vec.size(); i += 2) {
		ans += min(vec[i], vec[i + 1]);
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {

	var A, B, C, K int
	fmt.Scanf("%d %d %d %d", &A, &B, &C, &K)

	var result int
	if A < K {
		if (A + B) < K {
			result = 1*A + 0*B + -1*(K-A-B)
		} else {
			result = 1*A + 0*(K-A)
		}
	} else {
		result = 1 * K
	}

	fmt.Println(result)
}


Measured memory_bytes: 1832
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <stdio.h>
#include <cmath>
#include <math.h>
#include <sstream>
#include <iomanip>
#include <time.h>
#include <fstream>

using namespace std;

long long maxLL (long long a, long long b){
	if (a>b) return a;
	return b;
}

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

	int f[n][10];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < 10; j++){
			cin>>f[i][j];
		}
	}
	long long p[n][11];
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= 10; j++){
			cin>>p[i][j];
		}
	}
	long long total = -100*10e7*10*10;
	for(int i = 1 ; i < 1024; i++){
		long long current = 0;

		int code[10];
		int binary = i;
		for(int k = 0; k < 10; k++){
			code[k] = binary % 2;
			binary /= 2;
		}

		for(int j = 0 ; j < n; j++){
			int common = 0;
			for(int k = 0; k < 10; k++){
				if ((f[j][k] == 1) && (code[k] == 1)) common++;
			}
			current += p[j][common];
		}
		total = maxLL(current, total);
	}
	cout<<total<<endl;


	return 0;
}

Measured memory_bytes: 256
using System;

public class Hello
{
    public static void Main()
    {
        var s = Console.ReadLine().Trim();
        Console.WriteLine(check(s) ? "AC":"WA");
    }
    public static bool check (string s)
    {
        var sL = s.Length;
        if (s[0] != 'A') return false;
        var s2 = s.Substring(2, sL - 3);
        var a = s2.Length - s2.Replace("C", "").Length;
        if (a != 1) return false;
        var count = 0;
        for (int i = 1; i < s.Length; i++)
            if (Char.IsUpper(s[i])) count++;
        if (count == 1) return true;
        else return false;
    }
}


Measured memory_bytes: 11092
import java.util.Scanner;

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

		for (int i=1; i<=9&&k>0; i++){
			System.out.println(i);
			k--;
		}
		for (int i=1; i<=9&&k>0; i++){
			System.out.println(i*10+9);
			k--;
		}
		for (int e=2; e<=10&&k>0; e++){
			long a = (long)Math.pow(10, e);
			for (int i=e-1; i<=10*e-1&&k>0; i++){
				System.out.println((i+1)*a-1);
				k--;
			}
		}
		for (int i=11-1; i<=10*(11-1)-1&&k>0; i++){
			System.out.println((i+1)*(long)Math.pow(10,11)-1);
			k--;
		}
		for (int e=12; k>0; e++){
			long a = (long)Math.pow(10,e);
			for (int i=e-2; i<=10*(e-1)-1&&k>0; i++){
				System.out.println((i+1)*a-1);
				k--;
			}
		}
	}
}

Measured memory_bytes: 22740
object Main extends App {
var get1 = readLine.split(" ")
var loop = get1(1).toInt
var word = readLine
var count : Array[Int] = new Array(word.size)
	for(i <- 1 to word.size - 1) {
    	count(i) = 
     		if(word(i-1)=='A' && word(i)=='C') count(i - 1) + 1 
    		else count(i - 1)
    }
  	for(i <- 0 to loop - 1) {
      var position = readLine.split(" ")
    	println(count(position(1).toInt - 1) - count(position(0).toInt - 1))
    }
}

Measured memory_bytes: 46752
using System;

namespace abc168_b
{
    class Program
    {
        static void Main(string[] args)
        {
            int k = int.Parse(Console.ReadLine());
            string s = Console.ReadLine();
            if (s.Length > k)
            {
                Console.WriteLine(s.Substring(0,k) + "...");
            }
            else
            {
                Console.WriteLine(s);
            }
        }
    }
}


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

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define ALL(v) v.begin(),v.end()
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cout<<v[i]<<" "

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<ll, ll> P;
struct Edge{ll from, to, cost;};
struct node{ll cost, to;
  bool friend operator>(node a, node b){
    return a.cost>b.cost;
  }
};

ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

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

ll modinv(ll a, ll mod){
  return modpow(a, mod-2, mod);
}

ll gcd(ll a, ll b){
  ll r = a%b;
  if(r==0) return b;
  else return gcd(b, a%b);
}

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}


/**************************************
** A main function starts from here  **
***************************************/
int main(){
  ll M, K;
  cin >> M >> K;
  if(M==0){
    if(K==0){
      cout << "0 0";
    }else{
      cout << -1;
    }
  }else if(M==1){
    if(K==0){
      cout << "0 0 1 1";
    }else{
      cout << -1;
    }
  }else{
    if(K<=pow(2,M)-1){
      rep(i, pow(2,M)){
        if(i!=K){
          cout << i << " ";
        }
      }
      cout << K << " ";
      rep(i, pow(2,M)){
        if((pow(2,M)-1-i)!=K){
          cout << pow(2, M)-1-i << " ";
        }
      }
      cout << K;
    }else{
      cout << -1;
    }
  }
  return 0;
}


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

using namespace std;

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)

struct edge{
	lli to,cost;
};
#define P pair<lli,lli>

lli n;
lli dist[100100];
vector<vector<edge>> g;

void func(lli now,lli from){
	for(auto &e:g[now]){
		if(e.to==from)continue;
		dist[e.to]=dist[now]+e.cost;
		func(e.to,now);
	}
}

signed main(){

	cin>>n;
	g.resize(n);

	REP(i,0,n-1){
		lli a,b,c;
		cin>>a>>b>>c;
		a--,b--;
		g[a].push_back({b,c});
		g[b].push_back({a,c});
	}

	lli q,k;

	cin>>q>>k;
	k--;
	dist[k]=0;
	func(k,-1);

	/*
	REP(i,0,n){
		cout<<"i="<<i<<" dist="<<dist[i]<<endl;
	}*/

	REP(i,0,q){
		lli x,y;
		cin>>x>>y;
		x--,y--;
		cout<<dist[x]+dist[y]<<endl;
	}



	return 0;
}

Measured memory_bytes: 14336
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ll long long
#define lld long double
#define ALL(x) x.begin(), x.end()
using namespace std;

const int IINF = 1 << 30;
const ll INF = 1ll << 60;
const ll MOD = 1e9 + 7;

ll mpow(ll base, ll num)
{
    if (num == 0)
        return 1;
    ll prev = mpow(base, num / 2);
    if (num % 2 == 0)
    {
        return (prev * prev) % MOD;
    }
    else
    {
        return ((prev * base) % MOD * prev) % MOD;
    }
}

const int MAX = 510000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll calc(ll n)
{
    ll frac = 1;
    ll div = 1;
    rep(i, n - 1)
    {
        frac *= (n + 1 + i);
        frac %= MOD;
    }
    rep(i, n - 1)
    {
        div *= (n - 1 - i);
        div %= MOD;
    }
    cerr << frac << " " << div << endl;
    return (frac * mpow(div, MOD - 2)) % MOD;
}

int main(int argc, char const *argv[])
{
    ll n, k;
    cin >> n >> k;
    COMinit();
    assert(COM(n, 1) == n);
    if (k > n - 1)
        k = n - 1;
    ll ans = calc(n);
    //cerr << ans << endl;
    for (ll i = n - 1; i > k; i--)
    {
        ll j = n - i;
        ans -= (COM(n, j) * COM(n - 1, j - 1)) % MOD;
        //cerr << COM(n, j) << " " << COM(n - 1, j - 1) << endl;
        if (ans < 0)
            ans += MOD;
        //cerr << ans << endl;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 12160
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main(void){
    long long int i, j, n, x, t, ans=0, po=0;
    scanf("%lld", &n);
    long long int a[n];
    for(i=0; i<n; i++) scanf("%lld", &a[i]);
    
    for(i=1; i<n; i++){
        if(a[i]<a[i-1]){
            ans += a[i-1] - a[i];
            a[i] = a[i-1];
        }
    }
    printf("%lld", ans);
    
}

Measured memory_bytes: 3288
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
#include<vector>
#include<queue>
#include<deque>
#include<iomanip>
#include<map>
using namespace std;
typedef pair<int, pair<int, int> >PP;
typedef long long ll;
typedef pair<int, int>P;
typedef vector<int>vec;
int inf=-1;
ll mod = pow(10, 9) + 7;

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

    if(s=="Sunny"){
        cout<<"Cloudy"<<endl;
    }
    else if(s=="Cloudy"){
        cout<<"Rainy"<<endl;
    }
    else{
        cout<<"Sunny"<<endl;
    }
    return 0;
}

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

typedef long long ll;
const int MOD = 1000000007;

int main(){
  int N;
  cin >> N;
  string S1,S2;
  cin >> S1 >> S2;
  ll dp[N+1];
  fill((ll*)dp, (ll*)dp + sizeof(dp)/sizeof(ll), 0);
  int flag = 0;
  if(S1[0] != S2[0]) flag = 1;
  if(flag == 1) dp[0] = 6;
  else dp[0] = 3;
  for(int i = 1; i < N; i++){
    if(flag == 1){
      dp[i] = dp[i-1];
      flag = 2;
      continue;
    }
    if(S1[i] == S2[i]){
      if(flag == 0){
	dp[i] = dp[i-1] * 2 % MOD;
      }else{
	dp[i] = dp[i-1];
	flag = 0;
      }
    }else{
      if(flag == 0){
	dp[i] = dp[i-1] * 2 % MOD;
	flag = 1;
      }else{
	dp[i] = dp[i-1] * 3 % MOD;
	flag = 1;
      }
    }
  }
  cout << dp[N-1] << endl;
}


Measured memory_bytes: 256
/*
https://atcoder.jp/contests/dp/tasks/dp_c
*/
import java.io.*;
import java.util.*;

public class Main {
    private static int n;
    private static int[][] arr;
    private static int[][] dp;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n][4];
        dp = new int[n][4];
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= 3; j++) {
                arr[i][j] = sc.nextInt();
                dp[i][j] = -1;
            }
            dp[i][0] = -1;
        }

        System.out.println(solve(0, 0)); // solve(day,choosen on previous day)
    }

    private static int solve(int day, int flag) {
        if (day == n) {
            return 0;
        }

        if (dp[day][flag] != -1) {
            return dp[day][flag];
        }

        int max = 0;
        for (int i = 1; i <= 3; i++) {
            if (i != flag) {
                max = Math.max(max, arr[day][i] + solve(day + 1, i));
            }
        }
        return dp[day][flag] = max;
    }
}

Measured memory_bytes: 110740
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int s[501],q[1001][5];
int main()
{
	int i,j,n,m,a,b,c;
	while(cin>>a>>b>>c)
	{
		if(a==0&&b==0&&c==0)break;
		cin>>n;
		for(i=1;i<=500;i++)s[i]=2;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=4;j++)
			{
				cin>>q[i][j];
			}
			if(q[i][4]==1)
			{
				s[q[i][1]]=1;
				s[q[i][2]]=1;
				s[q[i][3]]=1;
			}
		}
		for(i=1;i<=n;i++)
		{
			if(s[q[i][1]]==1&&s[q[i][2]]==1&&q[i][4]==0)s[q[i][3]]=0;
			else if(s[q[i][1]]==1&&s[q[i][3]]==1&&q[i][4]==0)s[q[i][2]]=0;
			else if(s[q[i][3]]==1&&s[q[i][2]]==1&&q[i][4]==0)s[q[i][1]]=0;
		}
		for(i=1;i<=a+b+c;i++)
		{
			cout<<s[i]<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 2992
#include <iostream>
#include <cmath>
#define inf 2000000005

using namespace std;

int x, y;

int dist(int i, int j)
{
	if(i > j) return inf;
	return j - i;
}

int main(void)
{
	cin >> x >> y;
	int ans = inf;
	
	ans = min(ans, dist(x, y));
	ans = min(ans, dist(-x, y)+1);
	ans = min(ans, dist(x, -y)+1);
	ans = min(ans, dist(-x, -y)+2);
	
	cout << ans << endl;
	return 0;
}

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

int main(){
    int n;
    cin >> n;
    int end_a = 0;
    int start_b = 0;
    int start_b_and_a = 0;
    int include_ab = 0;
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        if(s.at(0) == 'B' && s.at(s.size()-1) != 'A'){
            start_b++;
        }
        if(s.at(0) != 'B' && s.at(s.size()-1) == 'A'){
            end_a++;
        }
        if(s.at(0) == 'B' && s.at(s.size()-1) == 'A'){
            start_b_and_a++;
        }
        for(int i = 0; i < s.size()-1; i++){
            if(s.at(i) == 'A' && s.at(i+1) == 'B'){
                include_ab++;
            }
        }
    }
    int ans = include_ab;
    if(start_b + end_a == 0 && start_b_and_a > 0){
        ans += start_b_and_a - 1;
    } else {
        ans += start_b_and_a + min(start_b, end_a);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
from math import gcd
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
mod = 1000000007

#%%

kai = [1]*(n+1)
gyaku = [1]*(n+1)

for i in range(2, n+1):
    kai[i] = kai[i-1]*i % mod
    gyaku[i] = gyaku[i-1]*pow(i, mod-2, mod) %mod

azero = 0
bzero = 0
zerozero = 0
dict_patterns = {}
dict_patterns_minus = {}
all_effective = 0
answer = 0
dict_patterns["1,0"] = 0
dict_patterns["0,-1"] = 0

for i in range(n):
    minus = False
    a, b = ab[i]
    if a == 0 and b == 0:
        zerozero += 1
        continue
    elif b == 0:
        dict_patterns["1,0"] += 1
        continue
    elif a == 0:
        dict_patterns["0,-1"] += 1
        continue
    
    common = gcd(a,b)
    a = a//common
    b = b//common
    
#%%
    
    if a < 0 and b < 0:
        a = -a
        b = -b
    elif a < 0:
        a = -a
        b = -b
    
    
    to_str = str(a)+","+str(b)
    if to_str not in dict_patterns:
        dict_patterns[to_str] = 1
    else:
        dict_patterns[to_str] += 1


keys = list(dict_patterns.keys())
patterns = []
test = []
for i in range(len(keys)):
    pattern_A = dict_patterns[keys[i]]
    dict_patterns[keys[i]] = 0
    pattern_B = 0
    a, b = map(int, keys[i].split(","))
    
    if str(b)+","+str(-a) in dict_patterns:
        pattern_B += dict_patterns[str(b)+","+str(-a)]
        dict_patterns[str(b)+","+str(-a)] = 0
    if str(-b)+","+str(a) in dict_patterns:
        pattern_B += dict_patterns[str(-b)+","+str(a)]
        dict_patterns[str(-b)+","+str(a)] = 0
    if pattern_A != 0 or pattern_B != 0:
        patterns.append(max(2**pattern_A-1,0) + max(2**pattern_B-1,0)+1)  
    test.append([pattern_A, pattern_B])

answer = 1
for i in range(len(patterns)):
    answer = answer*patterns[i] % mod

print((answer-1+zerozero)%mod)



Measured memory_bytes: 174692