akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,Q=map(int,input().split())
class RangeBIT:
    def __init__(self,n):
        self.p=self.BIT(n+1)
        self.q=self.BIT(n+1)
    
    def add(self,s,t,x):
        self.p.add(s,-x*s)
        self.p.add(t,x*t)
        self.q.add(s,x)
        self.q.add(t,-x)
    
    def sum(self,s,t):
        return self.p.sum(t)+self.q.sum(t)*t-self.p.sum(s)-self.q.sum(s)*s
    
    def f(self,i):
        return self.sum(i,i+1)
    
    class BIT:
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s

ly,lx=N-1,N-1
by,bx=RangeBIT(N),RangeBIT(N)
ans=0
for _ in range(Q):
    a,x=map(int1,input().split())
    if a==0:
        if x>lx:
            res=bx.f(x)
            ans+=res
        else:
            ans+=ly-1
            bx.add(x,lx,ly-1)
            lx=x
    else:
        if x>ly:
            res=by.f(x)
            ans+=res
        else:
            ans+=lx-1
            by.add(x,ly,lx-1)
            ly=x
print((N-2)**2-ans)

Measured memory_bytes: 76092
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
#define N 200005

int main()
{
    int n,k;
    cin>>n>>k;
    k*=2;
    k++;
    cout<<(n+k-1)/k;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int infty = 1<<28;
struct Node{
  vector<int> con;
  vector<int> cost;
  vector<int> dist;
};
struct State{
  int L;
  int cost;
  int now;
  State():now(-1),cost(infty),L(-1){}
  State(int pos,int cost, int L):now(pos),cost(cost),L(L){}
  bool operator>(const State &t)const{return cost>t.cost;}
};
typedef vector<Node> Graph;
int dijkstra(int s, int g, int L, Graph &G){
  int A[G.size()][L+1];
  bool vis[G.size()][L+1];
  for(int i = 0; i < G.size(); ++i){
    for(int j = 0; j < L+1; ++j){
      A[i][j]=infty;
      vis[i][j]=false;
    }
  }
  priority_queue<State,vector<State>,greater<State> > Q;
  Q.push( State(s,0,L) );
  if(s==g)return 0;
  while(!Q.empty()){
    State now = Q.top(); Q.pop();
    if(vis[now.now][now.L])continue;
    vis[now.now][now.L]=true;
    for(int i = 0; i < G[now.now].con.size(); ++i){
      int next_id = G[now.now].con[i];
      for(int k = 0; k < 2; ++k){
	int next_L = now.L - G[now.now].dist[i];
	int costi = G[now.now].cost[i];
	if(k==1)next_L=now.L;
	if(k==0)costi=0;
	if(next_L>=0){
	  if( now.cost+costi<A[next_id][next_L] ){
	    A[next_id][next_L]=now.cost+costi;
	    if(!vis[next_id][next_L]){
	      Q.push(State(next_id,A[next_id][next_L],next_L));
	    }
	  }
	}
      }
    }
  }
  int ret=infty;
  for(int i = 0; i < L+1; ++i){
    ret=min(ret,A[g][i]);
  }
  return ret;
}


int main()
{
  int N,M,L;
  while(cin>>N>>M>>L&&N){
    Graph G(N);
    for(int i = 0; i < M; ++i){
      int A,B,D,E;
      cin >> A >> B >> D >> E;
      --A;--B;
      G[A].con.push_back(B);
      G[A].cost.push_back(E);
      G[A].dist.push_back(D);
      G[B].con.push_back(A);
      G[B].cost.push_back(E);
      G[B].dist.push_back(D);
    }
    cout << dijkstra(0,N-1,L,G) << endl;
  }
  return 0;
}

Measured memory_bytes: 1460
#include<iostream>
#include<string>
using namespace std;
int main(){
	string map="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
	int n,k[100];
	while(true){
	cin>>n;
	if(n==0)
		break;
	for(int i=0;i<n;i++)
		cin>>k[i];
	string s;
	cin>>s;
	for(int i=0;i<s.size();i++){
		int x;
		for(int j=0;j<map.size();j++){
			if(map[j]==s[i])
				x=j;
		}
		x-=k[i%n];
		if(x<0)
			x+=map.size();
		cout<<map[x];
	}
	cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 1212
#include<iostream>
 #include<stdio.h>
 #include<string>
 #include<math.h>
 #include<iomanip>
 #include<algorithm>
 #include<string.h>
 #include<cctype>
 #include<map>
 #include<set>
 #include<vector>
 #include<sstream>
 #include<stack>
 #include<queue>
 
 using namespace std;
 
 int main()
 {
   int a,b;
   cin>>a>>b;
   cout<<(a*b)<<" "<<2*(a+b)<<endl;
   //while(1);
   return 0;
 }
 
 
 

Measured memory_bytes: 3008
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<cmath>
#include<cstdio>

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

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

int K;

int main(int argc, const char * argv[]) {
    
    cin >> K;
    
    ll c=0;
    ll num=7;
    bool isK=false;
    while(c<=K){
        c++;
        if(num%K==0){
            isK=true;
            break;
        }
        num = num%K;
        num = (num * 10 + 7);
    }
    
    if(isK) cout << c << endl;
    else cout << "-1" << endl;
    
    return 0;
}


Measured memory_bytes: 3132
#include <stdio.h>
#include <string.h>
#define MAX 1001

void print(int, int);
void reverse(int, int);
void replace(int, int, char []);

char str[MAX];

int main(void) {
    int n, a, b;
    char buf[8], ptn[MAX];
    scanf("%s", str);
    for(scanf("%d", &n); n--;) {
        scanf("%s %d %d", buf, &a, &b), b++;
        switch(strcmp("replace", buf)) {
          case 1:
            print(a, b);
            break;
          case 0:
            scanf("%s", ptn);
            replace(a, b, ptn);
            break;
          case -1:
            reverse(a, b);
            break;
        }
    }
    return 0;
}

void print(int a, int b) {
    char buf[MAX] = {};
    printf("%s\n", strncat(buf, str + a, b - a));
}

void reverse(int a, int b) {
    int i;
    char buf[MAX] = {};
    strncat(buf, str, a);
    for(i = 0; i < b - a; i++) {
        buf[a + i] = str[b - i - 1];
    }
    strcat(buf, str + b);
    strcpy(str, buf);
}

void replace(int a, int b, char ptn[]) {
    char buf[MAX] = {};
    strncat(buf, str, a);
    strcat(buf, ptn);
    strcat(buf, str + b);
    strcpy(str, buf);
}

Measured memory_bytes: 608
# -*- coding:utf-8 -*-

def solve():
    N = int(input())
    MOD = 10**9+7

    """考え方
    ・6の約数の個数は？
    6を素因数分解すると
    6 = 2 * 3
    2^(k1) * 3^(k2) （0<= k1,k2 <= 1）の組み合わせが約数（1,2,3,6）

    この約数の個数を求める問題は、「|k1|個のボールと|k2|個のボールを取り出す組み合わせ問題」と同じ。

    というふうに、まず素因数分解をして因数のknをそれぞれ求めて、その組合せの数を求めれば良い。
    """

    dic = {}  # dic[p] := 因数pの個数（ただしp^0も含めたいので初期値は1する）

    for n in range(2, N+1):
        num = n
        i = 2
        while True:
            if i > num: break

            if num%i == 0:
                num = num / i
                if not i in dic: dic[i] = 1
                dic[i] += 1
                continue
            else:
                i += 1
                continue

    ans = 1
    for key, value in dic.items():
        ans *= value
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    solve()


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

int main(void)
{

    char s[10000];
    char t[10000];

    int i, j;
    int c_min, count;

    cin >> s;
    cin >> t;

    c_min = 10000;

    i = 0;
    while(1){
        if(s[i] == '\0'){
            break;
        }

        j = 0;
        count = 0;
        while(1){
            if(t[j] == '\0'){
                break;
            }

            if(s[i + j] != t[j]){
                count++;
            }
            j++;
        }

        if(count < c_min){
            c_min = count;
        }

        if(s[i+j] == '\0'){
            break;
        }

        i++;

    }

    cout << c_min;

    return 0;

}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i <= (n); ++i)
#define Sort(Array) sort(Array.begin(), Array.end())
#define Reverse(a) reverse(a.begin(), a.end())
#define out(ans) cout << ans << endl;

int main(){
  int N, K;
  cin>>N>>K;
  int A[101]={0};
  rep(i, K){
    int d;
    cin>>d;
    rep(j, d){
      int a;
      cin>>a;
      A[a-1]++;
    }
  }

  int ans=0;

  rep(i, N){
    if(A[i]==0) ans++;
  }
  cout<<ans<<endl;

  }


Measured memory_bytes: 3640
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int X = sc.nextInt();

		int[] m = new int[N];

		int rem = X;
		int ans = 0;
		int minVal = 0;
		for (int i = 0; i < N; i++){
			m[i] = sc.nextInt();
			if (i == 0){ // 初回のみ
				minVal = m[i];
			}
			rem -= m[i];
			minVal = Math.min(minVal, m[i]);
			ans++;
		}

		ans += rem / minVal;

		System.out.println(ans);
	}
}


Measured memory_bytes: 23764
#include<bits/stdc++.h>
using namespace std;
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int n,k,s=0;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n,cmp);
    for(int i=0;i<k;i++)
    {
        s+=a[i];
    }
    cout<<s<<endl;
    return 0;
}

Measured memory_bytes: 256
//
//  main.cpp
//  Irreversibele_Operation
//
//  Created by Uttam Datta on 03/06/19.
//  Copyright © 2019 Uttam Datta. All rights reserved.
//

#include <iostream>
#include <vector>
using namespace std;



string S;

long long int ans(){
    long long int res = 0;
    long long int blacks = 0;
    for(long long int i = 0; i < S.size(); i++){
        if(S[i] == 'B'){
            blacks++;
        }
        else{
            res += blacks;
        }
    }
    return res;
    
}


int main(){
    
    cin >> S;
    cout << ans() << endl;
    return 0;
    
    
}




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

int main() {
   int n;
   cin >> n;
   int m = n;
   int sum = 0;
   while(m) {
      sum += m % 10;
      m /= 10; 
      }
   cout <<(n % sum == 0 ? "Yes" : "No")<< endl;  
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#define ll long long
using namespace std;
int main() {
    ll N=0, K=0;
    cin >> N >> K;
    vector<ll> H(N);
    for (ll i=0; i<N; ++i) {
        cin >> H[i];
    }
    sort(H.begin(), H.end(), greater<ll>());
    ll num = 0;
    for (ll i=K; i<N; ++i) {
        num += H[i];
    }
    cout << num << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

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

    int a, b;
    cin >> a >> b;
    if (a + b == 15)
        cout << "+" << endl;
    else if (a * b == 15)
        cout << "*" << endl;
    else
        cout << "x" << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
const int N = 200005;
 
int n, cur = N, a[N];
long long ans = 0;
 
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", a + i);
    for (int i = n - 1; i >= 0; i--)
        if (i - a[i] != cur)
        {
            if (i - a[i] < 0 || i - a[i] > cur)
            {
                printf("-1");
                return 0;
            }
            else
            {
                cur = i - a[i];
                ans += a[i];
            }
        }
    printf("%lld", ans);
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
using namespace std;

void solve(){
    int q, x;
    // char com[20];
    string com;

    list<int> v;
    // scanf("%d", &q);
    cin >> q;
    rep(i, 0, q){
        // scanf("%s", com);
        cin >> com;
        if(com[0] == 'i'){
            // scanf("%d", &x);
            cin >> x;
            v.push_front(x);
        }else if(com[6] == 'L'){
            v.pop_back();
        }else if(com[6] == 'F'){
            v.pop_front();
        }else if(com[0] == 'd'){
            // scanf("%d", &x);
            cin >> x;
            for(auto it = v.begin(); it != v.end(); it++){
                if(*it == x){
                    v.erase(it);
                    break;
                }
            }
        }
    }
    int i = 0;
    for(auto it = v.begin(); it != v.end(); it++){
        if(i++) printf(" ");
        printf("%d", *it);
    }
    printf("\n");
}


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

    solve();
    return 0;
}



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

int main(int argc, const char * argv[]) {
    int X, N;
    cin >> X;
    cin >> N;
    if (N == 0) {
        cout << X;
        return 0;
    }
    
    vector<int> p;
    for (int i = 0; i < N; i++) {
        int tmp;
        cin >> tmp;
        p.push_back(tmp);
    }
    
    sort(p.begin(), p.end());
        
    auto itr = find(p.begin(), p.end(), X);
    if (itr == p.end()) {
        cout << X;
        return 0;
    }
    
    int ans = 0;
    int t0 = X - 1;
    int t1 = X + 1;
    while(true){
        {
            auto itr = find(p.begin(), p.end(), t0);
            if (itr == p.end()) {
                ans = t0;
                break;
            }
            t0 -= 1;
        }
        
        {
            auto itr = find(p.begin(), p.end(), t1);
            if (itr == p.end()) {
                ans = t1;
                break;
            }
            t1 += 1;
        }
    }
    
    std::cout << ans;
    return 0;
}

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

int main(void) {
  int N, K;
  cin >> N >> K;
  vector<int> p(N);
  vector<double> tmp(N);
  for (int i = 0; i < N; i++) {
    cin >> p[i];
    tmp[i] = ((p[i] * (p[i] + 1)) / 2) / (double)p[i];
  }
  double ans = 0.0;
  for (int i = 0; i < K; i++) {
    ans += tmp[i];
  }
  double current = ans;
  for (int i = K; i < N; i++) {
    current -= tmp[i - K];
    current += tmp[i];
    ans = max(ans, current);
  }
  cout << fixed << setprecision(7) << ans << endl;
  return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define PI 3.141592653589793
#define MOD 1000000007
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(v) v.begin(), v.end()

typedef long long ll;
typedef long double ld;

int main() {
    string str;
    cin >> str;
    queue<string> que;
    string tmp[4] = {"dream", "dreamer", "erase", "eraser" };

    rep(i,4) que.push(tmp[i]);

    while(!que.empty()){
        string s;
        s = que.front();
        que.pop();
        rep(i,4){
            string tmp_s = s + tmp[i];
            if(tmp_s.size() < str.size() && str.substr(0,tmp_s.size()) == tmp_s){
                que.push(tmp_s);
            }
            else if(tmp_s.size() == str.size() && str == tmp_s){
                cout << "YES" << endl;
                return 0;
            }
        } 
    }
    cout << "NO" << endl;

}

Measured memory_bytes: 4340
#include <bits/stdc++.h>
#define ALL(A) (A).begin(), (A).end()
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

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

const ll mod = 1e9 + 7;
const ll INF = -1 * ((1LL << 63) + 1);
const int inf = -1 * ((1 << 31) + 1);

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    char a;
    cin >> a;
    if(a >= 'a')cout << "a" << endl;
    else cout << "A" << endl;
}

Measured memory_bytes: 3576
#include<bits/stdc++.h>
using namespace std;
#define N 510
int n;
int c[N],s[N],f[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;++i)
		scanf("%d%d%d",&c[i],&s[i],&f[i]);
	for(int i=1;i<=n;++i)
	{
		int ans=0;
		for(int j=i;j<n;++j)
		{
			if(ans<s[j]) ans=s[j];
			if(ans>s[j]) 
			{
				int t=(ans-s[j])/f[j];
				if((ans-s[j])%f[j])
					ans=s[j]+(t+1)*f[j];
				else ans=s[j]+t*f[j];
			}
			ans+=c[j];
		}
		printf("%d\n",ans);
	}
	return 0;
}


Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 1000000007;

long long int power(long long int x, long long int n, long long int M) {
	long long int tmp = 1;

	if (n > 0) {
		tmp = power(x, n / 2, M);
		if (n % 2 == 0) tmp = (tmp*tmp) % M;
		else tmp = (((tmp*tmp) % M)*x) % M;
	}
	return tmp;
}

long long int N, M, K, Q, W, H, L, R;
long long int ans;

using namespace std;


int main() {
	ios::sync_with_stdio(false);
	cin >> N >> M;
	if (M == 1 || M == 2 * N - 1) {
		cout << "No\n";
		return 0;
	}
	cout << "Yes\n";
	if (N == 2) {
		cout << "1 2 3\n";
		return 0;
	}
	int num[500000] = {};
	bool flag[500000] = {};
	flag[M] = true;
	flag[M - 1] = true;
	flag[M + 1] = true;
	num[N] = M;
	num[N - 1] = M - 1;
	num[N + 1] = M + 1;
	if (M != 2 * N - 2) {
		num[N - 2] = M + 2;
		flag[M + 2] = true;
	}
	if (M != 2) {
		num[N + 2] = M - 2;
		flag[M-2] = true;
	}
	int box = 1;
	for (int i = 1; i <= N * 2 - 1; i++) {
		if (num[i])continue;
		while (flag[box])box++;
		num[i] = box;
		flag[box] = true;
	}
	for (int i = 1; i <= 2 * N - 1; i++) {
		cout << num[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 3968
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <iomanip>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;

LL dist[20][100][100];
LL fare[100][100];
const LL M=1LL<<60;
LL p[20];
LL q[20][50];
LL r[20][50];
int n,m,c,s,g;
int main() {
while(1){
	cin >> n >> m >> c >> s >> g;
	if((n|m|c|s|g)==0)return 0;
	s--;g--;
	for(int i=0;i<c;i++){
		for(int j=0;j<n;j++){
			for(int k=0;k<n;k++){
				dist[i][j][k]=M;
			}
			dist[i][j][j]=0;
		}
	}
	for(int i=0;i<m;i++){
		int x,y,d,c;
		cin >> x >> y >> d >> c;
		x--;y--;c--;
		dist[c][x][y]=dist[c][y][x]=min(dist[c][x][y],(LL)d);
	}
	for(int a=0;a<c;a++){
		for(int k=0;k<n;k++){
			for(int i=0;i<n;i++){
				for(int j=0;j<n;j++){
					dist[a][i][j]=min(dist[a][i][j],dist[a][i][k]+dist[a][k][j]);
				}
			}
		}
	}
	for(int i=0;i<c;i++){
		cin >> p[i];
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			fare[i][j]=M;
		}
	}
	for(int i=0;i<c;i++){
		for(int j=0;j<p[i]-1;j++){
			cin >> q[i][j];
		}
		q[i][p[i]-1]=M;
		for(int j=0;j<p[i];j++){
			cin >> r[i][j];
		}
		for(int j=0;j<n;j++){
			for(int k=0;k<n;k++){
				LL d=dist[i][j][k];
				if(d==M)continue;
				LL last=0;
				LL sum=0;
				for(int t=0;t<p[i];t++){
					if(d<=q[i][t]){
						sum+=(d-last)*r[i][t];
						break;
					}
					else{
						sum+=(q[i][t]-last)*r[i][t];
						last=q[i][t];
					}
				}
				fare[j][k]=min(fare[j][k],sum);
			}
		}
	}
	for(int k=0;k<n;k++){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				fare[i][j]=min(fare[i][j],fare[i][k]+fare[k][j]);
			}
		}
	}
	if(fare[s][g]<M){
		cout << fare[s][g] << endl;
	}
	else{
		cout << -1 << endl;
	}
}
}

Measured memory_bytes: 2824
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include<climits>
using namespace std;

#define ll long long
#define tc                int T;cin>>T;while(T--)
int a[100000];
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
	int n, c, b ; cin >> n;
	for (int& e : a)cin >> e;
	vector<int> dp(n, INT_MAX);
	dp[0] = 0;
	for (int i = 0; i < n; ++i) {
		for (int e : {i + 1, i + 2}) {
			if (e < n)
					dp[e] = min(dp[e],dp[i] + abs(a[e] - a[i]));
		}
	}
	cout << dp[n - 1] << '\n';
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}

using int64 = long long;

int main() {
    int n;
    cin >> n;
    vector a(n,0);
    for (int i=0; i<n; i++) cin >> a[i];

    int ans = 0;
    for (int i=0; i<n; i+=2) {
        if (a[i]%2) ans++;
    }

    cout << ans << endl;
}

Measured memory_bytes: 3108
#include<bits/stdc++.h>
#define INF 1000000001
using namespace std;

int main()
{
  int V,E,r;scanf("%d %d %d",&V,&E,&r);
  int s[E],t[E],d[E],dist[V];vector<vector<int>> G(V);
  for(int i=0;i<E;i++)
  {
    scanf("%d %d %d",&s[i],&t[i],&d[i]);
    G[s[i]].push_back(t[i]);
  }
  bool check[V];fill(check,check+V,false);
  queue<int> S;S.push(r);
  while(!S.empty())
  {
    int i=S.front();check[i]=true;S.pop();
    for(int k : G[i])
    {
      if(check[k])continue;
      S.push(k);
    }
  }
  fill(dist,dist+V,0);int k=-1;
  for(int i=0;i<V;i++)for(int j=0;j<E;j++)if(check[s[j]]&&dist[t[j]]>dist[s[j]]+d[j]){dist[t[j]]=dist[s[j]]+d[j],k=i;}
  if(k==V-1){printf("NEGATIVE CYCLE\n");return 0;}
  fill(dist,dist+V,INF);dist[r]=0;
  while(true)
  {
    bool update=false;
    for(int i=0;i<E;i++)if(dist[s[i]]!=INF&&dist[t[i]]>dist[s[i]]+d[i])dist[t[i]]=dist[s[i]]+d[i],update=true;
    if(!update)break;
  }
  for(int i=0;i<V;i++)if(dist[i]==INF)printf("INF\n");else printf("%d\n",dist[i]);
}


Measured memory_bytes: 3296
#!/usr/bin/env ruby
# require 'pry'

# N
# a_1 b_1
# ...
# a_N b_N
# ↑を[[a_1,..a_N],[b_1,..b_N]]にする
# N = gets.to_i
# a, b = N.times.map{gets.split.map(&:to_i)}.transpose

n = gets.to_i
root_n = Integer.sqrt(n)
min_f = n.to_s.length
1.upto(root_n) do |i|
  if n % i == 0
    min_f = (n/i).to_s.length
  end
end

puts min_f

Measured memory_bytes: 14268
#include <iostream>
#include <string>
#include <iomanip>

using namespace std;

int main()
{
    int n, m = 0;
    double total = 0.0;
    cin >> n;
    double x;
    string u;

    for (int i = 0; i < n; i++)
    {
        cin >> x >> u;
        if (u == "JPY")
        {
            m = x;
            total += m;
        }
        if (u == "BTC")
        {
            total += 380000 * x;
        }
    }
    cout << fixed << setprecision(4) << total << endl;
    return (0);
}

Measured memory_bytes: 256
if __name__ == "__main__":
    h, w, k = map(int, input().split())
    s = []

    for _ in range(h):
        si = input()
        s.append(si)
    
    h_split = [0] * (h - 1)
    part = 0
    ans = float('inf')
    for mask in range(1 << (h - 1)):
        g = 0
        g_id = [0] * h
        for i in range(h):
            g_id[i] = g
            if mask >> i & 1 == 1:
                g += 1
        g += 1

        c = []
        for _ in range(g):
            c.append([0] * w)
        
        for i in range(h):
            for j in range(w):
                if s[i][j] == "1":
                    c[g_id[i]][j] += 1
        num = g - 1
        now = [0] * g

        for j in range(w):
            for i in range(g):
                now[i] += c[i][j]
            ok = True
            for i in range(g):
                if now[i] > k:
                    ok = False

            if not ok:
                num += 1
                now = [0] * g
                for i in range(g):
                    now[i] += c[i][j]
                ok = True
                for i in range(g):
                    if now[i] > k:
                        ok = False
                if not ok:
                    num = float('inf')
                    break
        ans = min(ans, num)
    print(ans)

Measured memory_bytes: 47196
n = int(input())
t, a = map(int, input().split())
h = list(map(int, input().split()))

x = int(round((t - a) / 0.006))

d = 100000
num = -1

for i, y in enumerate(h):
    if d > abs(y - x):
        d = abs(y - x)
        num = i

print(num + 1)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main(){
  int A,B,C,D;
  cin>>A>>B>>C>>D;
  if(A+B==C+D){
    cout<<"Balanced"<<endl;
    }
    
  else if(A+B>C+D){
    cout<<"Left"<<endl;
  }
  else if(A+B<C+D){
    cout<<"Right"<<endl;
  }
}



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

int n,tmp;
vector<int> li;

int main()
{
	int tot=0;
	scanf("%d",&n);
	for(int i=1;i<=2*n;i++)
	{
		scanf("%d",&tmp);
		li.push_back(tmp);
	}
	sort(li.begin(),li.end());
	for(int i=0;i<li.size();i+=2)
	{
		tot+=li[i];
	}
	printf("%d\n",tot);;
 	return 0;
}


Measured memory_bytes: 256
using System;
using System.IO;
using System.Text;

class Solve
{
    static void Main(string[] args) {
        var P = Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
        int x1 = P[0], x2 = P[2], y1 = P[1], y2 = P[3];
        var a = x2 - x1;
        var b = y2 - y1;
        var answers = new[] {x2 - b, y2 + a, x1 - b, y1 + a};
        var sb =new StringBuilder();
        for (int i = 0; i < 4; i++) {
            sb.Append(answers[i]).Append(' ');
        }
        var answer = sb.ToString();
        var writer = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
        Console.SetOut(writer);
        Console.WriteLine(answer);
        Console.Out.Flush();
    }
}

Measured memory_bytes: 27384
#include <stdio.h>

int get_type(char* s){
  if(s[0] == 'A'){
    if(s[1] == 'B'){
      return 2;
    }else{
      return 0;
    }
  }else if(s[0] == 'B'){
    return 1;
  }else if(s[0] == 'O'){
    return 3;
  }
  return 0;
}

int main(int argc, char *argv[]){
  int nums[4];
  nums[0] = nums[1] = nums[2] = nums[3]  = 0;
  char b_n[3];
  int number;

  while(scanf("%d,%s",&number,b_n) != EOF){
    nums[get_type(b_n)]++;
  }
  
  printf("%d\n%d\n%d\n%d\n",nums[0],nums[1],nums[2],nums[3]);
  
  return 0;    
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef long long ll;
ll bigmod(ll b,ll p){
    ll v=b,s=1LL;
    while(p>0LL){ if(p&1LL) s*=v,s%=mod; v*=v,v%=mod; p>>=1LL; }
    return s;
}
int main()
{
    ll n,a,b;
    cin>>n>>a>>b;
    ll ans=(bigmod(2LL,n)-1+mod)%mod;
    ll qa=1LL,pa=1LL;
    for(ll i=1LL;i<=a;i++)
        qa*=(n-i+1LL), qa%=mod, pa*=i, pa%=mod;
    ll qb=1LL,pb=1LL;
    for(ll i=1LL;i<=b;i++)
        qb*=(n-i+1LL), qb%=mod, pb*=i, pb%=mod;
    a=(qa*bigmod(pa,mod-2LL))%mod;
    b=(qb*bigmod(pb,mod-2LL))%mod;
    ans=(ans-a-b+mod)%mod;
    if(ans<0)ans+=mod;
    cout<<ans<<endl;
    return 0;
}


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

int main()
{
	cin.tie(nullptr); ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;

	cout << ((n == m) ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
// Ver19.02
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INF 1 << 29
#define LLINF 4545454545454545454
#define MOD 1000000007
#define ll long long
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
int upll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? -1 : *(ll *)a > *(ll *)b ? 1 : 0; }
int downll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? 1 : *(ll *)a > *(ll *)b ? -1 : 0; }
void sortup(ll *a, int n) { qsort(a, n, sizeof(ll), upll); }
void sortdown(ll *a, int n) { qsort(a, n, sizeof(ll), downll); }

int main()
{
  char x, y, space;
  scanf("%c%c%c", &x, &space, &y);
  if (x > y)
    puts(">");
  else if (x < y)
    puts("<");
  else
    puts("=");
  return 0;
}


Measured memory_bytes: 128
import math

def plot(x,y):
    print(f'{x:.8f} {y:.8f}')
    
def Koch(n,x1,y1,x2,y2):
    if n == 0:
        plot(x1,y1)
        return
    sx = (2*x1+x2)/3
    sy = (2*y1+y2)/3
    tx = (x1+2*x2)/3
    ty = (y1+2*y2)/3
    ux = (tx-sx)*(1/2)-(ty-sy)*(math.sqrt(3)/2)+sx
    uy = (tx-sx)*(math.sqrt(3)/2)+(ty-sy)*(1/2)+sy
    Koch(n-1,x1,y1,sx,sy)
    Koch(n-1,sx,sy,ux,uy)
    Koch(n-1,ux,uy,tx,ty)
    Koch(n-1,tx,ty,x2,y2)
    
n = int(input())
Koch(n,0,0,100,0)
plot(100,0)


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

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


Measured memory_bytes: 3628
#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 1e5 + 5;

vector<int> adj [MAX_N];
int dp [MAX_N][2];
// dp[u][i] -- is there a perf. matching in sub of u
// with u matched up if i is 1

void dfs (int u, int p) {
  int c00 = 0;
  int c01 = 0;
  int c10 = 0;
  int c11 = 0;
  for (int nxt : adj[u]) {
    if (nxt != p) {
      dfs(nxt, u);

      if (dp[nxt][0]) {
        if (dp[nxt][1]) {
          c11++;
        } else {
          c10++;
        }
      } else {
        if (dp[nxt][1]) {
          c01++;
        } else {
          c00++;
        }
      }
    }
  }

  if (c00 == 0) {
    // determine dp[u][1]
    dp[u][1] = (c01 == 0);

    // determine dp[u][0]
    dp[u][0] = (c01 <= 1) && (c01 + c11 > 0);
  }
}

int main () {
  ios::sync_with_stdio(false);

  int n;
  cin >> n;

  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;

    adj[u].push_back(v);
    adj[v].push_back(u);
  }

  dfs(1, 0);

  cout << (dp[1][0] ? "Second" : "First") << '\n';
}


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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { std::cout << #a << " = " << a << "\n"; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T, class V> istream& operator>> (istream& ist, pair<T, V>& p) { return ist >> p.first >> p.second; }
template<class T> ostream& operator<< (ostream& ost, pair<T, T>& p) { return ost << p.first << ", " << p.second; }
template<class T> istream& operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) ist >> e; return ist; }

typedef long long ll;
int const inf = INT_MAX / 2;

int main() {
  string S; cin >> S;
  int bcnt = 0;
  ll sum = 0;
  rep(i, S.size()) {
    if (S[i] == 'B') {
      bcnt++;
    } else {
      sum += bcnt;
    }
  }
  cout << sum << "\n";
}


Measured memory_bytes: 640
def main():
    N, M = map(int, input().split())
    commit = [list() for i in range(N)]

    for i in range(M):
        no, sta = input().split()
        commit[int(no)-1].append(sta)

    AC_total = 0
    WA_total = 0

    for i in range(len(commit)):
        WA = 0
        for j in range(len(commit[i])):
            if len(commit[i]) == 0:
                continue
            else:
                if commit[i][j] == "WA":
                    WA += 1
                elif commit[i][j] == "AC":
                    AC_total += 1
                    WA_total += WA
                    break
    print(AC_total, WA_total)
if __name__ == "__main__":
    main()

Measured memory_bytes: 20272
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n-1);i>=0;i--)
#define FOR(i,n,m) for(int i=n;i<=(int)(m);i++)
#define RFOR(i,n,m) for(int i=(int)(n);i>=m;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(std::unique(all(x)), x.end());
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
const double PI=acos(-1);
using namespace std;
vector<int> dx={1,0,-1,0};
vector<int> dy={0,1,0,-1};
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

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


Measured memory_bytes: 256
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        self.total += w
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def interval_sum(self, i, j):  # i <= x < j の区間
        return self.sum(j - 1) - self.sum(i - 1)

    def search(self, k):
        if k > self.total:
            return -1
        if k == 0:
            return 0
        step = 1 << (self.size.bit_length() - 1)
        now_index = 0
        ret = 0
        while step:
            if now_index + step < self.size and ret + self.bit[now_index + step - 1] < k:
                ret += self.bit[now_index + step - 1]
                now_index += step
            step >>= 1
        # now_indexを伸ばしいって、sumがk以上に達する直前まで伸ばし続けるならreturnのところでnow_index - 1。
        # その場合、bit.sum(now_index - 1) <= k < bit.sum(now_index)
        # 達してすぐのindexであれば-1しない
        return now_index


q = I()
query = []
A = []
for _ in range(q):
    l = LI()
    if l[0] == 1:
        A += [l[1]]
    query += [l]

ind_to_co = sorted(set(A))
co_to_ind = {}
for i, x in enumerate(ind_to_co):
    co_to_ind[x] = i

bit1 = BIT(len(A))
bit2 = BIT(len(A))
n = 0
B = 0
for l in query:
    if l[0] == 1:
        B += l[2]
        bit1.add(co_to_ind[l[1]], 1)
        bit2.add(co_to_ind[l[1]], l[1])
        n += 1
    else:
        center_ind = bit1.search(n // 2 + bool(n % 2))
        d = n // 2 + bool(n % 2)
        min_val = bit2.interval_sum(center_ind + 1, bit2.size) - bit1.interval_sum(center_ind + 1, bit1.size) * \
                  ind_to_co[center_ind] + bit1.sum(center_ind - 1) * ind_to_co[center_ind] - bit2.sum(center_ind - 1) + B
        print(ind_to_co[center_ind], min_val)

Measured memory_bytes: 111188
n = int(input())
L = [tuple(map(int, input().split())) for _ in range(n)]
for t, x, y in L:
    vio1 = x + y > t
    vio2 = t % 2 == 0 and (x + y) % 2 != 0
    vio3 = t % 2 != 0 and (x + y) % 2 == 0
    if vio1 or vio2 or vio3:
        print('No')
        exit()
print('Yes')

Measured memory_bytes: 17324
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    int cnt = 0;
    rep(i, n) {
        if(s[i] == 'R') cnt++;
    }

    int ans = 0;
    rep(i, cnt) {
        if(s[i] == 'W') ans++;
    }

    cout << ans << endl;
}

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

using namespace std;

int main() {
  int M, D; cin >> M >> D;
  int ans;
  for (int m = 1; m <= M; ++m) {
    for (int d = 10; d <= D; ++d) {
      int d_1 = d % 10, d_10 = d / 10;
      if (d_1 >= 2 && d_10 >= 2 && d_1 * d_10 == m) {
	++ans;
      }
    }
  }
  cout << ans << endl;
}
	   


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define INF (lo)(1e9 + 7)
#define MOD (lo)(1e9 + 7)
#define mp make_pair
#define pb push_back
#define pp pop_back
using namespace std;
typedef long long int lo;
string str;
string nstr;
int main(){
    cin >> str;
    for(lo i = 0;i < str.size();i++){
        char b = str[i];
        if(b == 'B'){
            if(nstr.size() == 0) continue;
            else nstr.pp();
        }
        else nstr.push_back(b);
    }
    cout << nstr;
    
}




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

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		List<String> list = new ArrayList<>();
		for(int i = 0; i < n; i++) {
			list.add(sc.next());
		}
		Collections.sort(list);
		List<Text> ans = new ArrayList<>();
		int max = 0;
		int num = 0;
		String b = "";
		for(String e : list) {
			if(ans.isEmpty()) {
				ans.add(new Text(e, 1));
				num++;
				continue;
			} else {
				Text ee = ans.get(ans.size() - 1);
				if(ee.getS().equals(e)) {
					ans.get(ans.size() - 1).setNum(ans.get(ans.size() - 1).getNum() + 1);
					num++;
				} else {
					max = Math.max(max, num);
					ans.add(new Text(e, 1));
					num = 1;
				}
			}
		}
		max = Math.max(max, num);
		for(Text e : ans) {
			if(e.getNum() == max) {
				System.out.println(e.getS());
			}
		}
	}

}

class Text {
	private String s;
	private int num;

	protected Text(String s, int num) {
		super();
		this.s = s;
		this.num = num;
	}

	public String getS() {
		return s;
	}

	public void setS(String s) {
		this.s = s;
	}

	public int getNum() {
		return num;
	}

	public void setNum(int num) {
		this.num = num;
	}

}

Measured memory_bytes: 84504
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <climits>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int INF=1<<29;
ll inf=1LL<<50;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll N,M,mod=1000000007;
	cin>>N>>M;
	vector<ll> a(M);
	for(int i=0;i<M;i++) cin>>a[i];

	ll dp[N+1];
	bool tab[N+1];
	for(int i=0;i<N+1;i++){
		dp[i]=0;
		tab[i]=false;
	}
	dp[0]=1;
	for(int i=0;i<M;i++) tab[a[i]]=true;

	for(int i=0;i<N+1;i++){
		//dp[i]=dp[i-1]+dp[i-2];
		if(tab[i]) continue;
		if(i==0) continue;
		else if(i==1){
			dp[i]+=dp[i-1];
		}else{
			dp[i]+=dp[i-1]+dp[i-2];
		}
		dp[i]%=mod;
	}
	cout<<dp[N]<<endl;

	return 0;
}

Measured memory_bytes: 1920
#include <iostream>
#include <cstdlib>
#include<vector>
#include<string>
#include<cmath>
#include <algorithm>
#include<complex>

using namespace std;
typedef long long LL;


int main() {
	LL N, K,x;
	LL A, B;
	LL total=0;
	vector<LL>vec;

	cin >> N >> K;
	for (LL i = 0; i < N; i++)
	{
		cin >> x;
		vec.push_back(x);
	}
	for (LL i = 0; i < vec.size(); i++)
	{
		A = abs(vec[i] - 0);
		B = abs(vec[i] - K);
		if (A>B)
		{
			total += 2 * B;
		}else{
			total += 2 * A;
		}
	}

	cout << total<<endl;

	return 0;
}


Measured memory_bytes: 256
use std::collections::HashMap;
fn main() {
    let n = read::<u32>();
    let mut inputs: Vec<String> = Vec::new();
    for _ in 0..n {
        let s = read::<String>();
        let chars = s.chars();
        let mut vec = chars.collect::<Vec<char>>();
        vec.sort();
        let mut s = String::new();
        for i in vec {
            s = format!("{}{}", s, i.to_string());
        }
        inputs.push(s);
    }
    inputs.sort();
    let mut count: u64 = 0;
    let mut m = HashMap::new();
    for s in &inputs {
        if m.contains_key(s) {
            let v = m[s];
            m.insert(s, v + 1);
        } else {
            m.insert(s, 1);
        }
    }
    for (_, &v) in &m {
        if v > 1 {
            count += v * (v - 1) / 2;
        }
    }
    println!("{}", count);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}


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

int main(void)
{
    int k, i = 0;
    char s[100];

    scanf("%d", &k);
    scanf("%s", s);

    while (1)
    {
        if (s[i] == '\0')
        {
            break;
        }
        if (i >= k)
        {
            printf("...");
            return 0;
        }
        else
        {
            printf("%c", s[i]);
        }
        i++;
    }

    return 0;
}

Measured memory_bytes: 3724
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

int h[16],w[16];
int dist[1<<16];
char ba[4][4];
int ok[1<<16];

int main() {
  int n;
  cin >> n;
  REP(i,n) cin >> h[i] >> w[i];
  REP(i,4) REP(j,4) cin >> ba[i][j];
  int num = 0;
  set<int> masks;
  REP(i,n) {
    for (int y1=-h[i]+1; y1<4; ++y1) {
      for (int x1=-w[i]+1; x1<4; ++x1) {
        int mask = 0;
        for (int y=y1; y<y1+h[i]; ++y) {
          for (int x=x1; x<x1+w[i]; ++x) {
            if (y>=0&&y<4&&x>=0&&x<4) mask |= 1<<(y*4+x);
          }
        }
        masks.insert(mask);
      }
    }
  }

  // FOR(it, masks) {
  //   int S = *it;
  //   REP(y,4) {
  //     REP(x,4)
  //       cout << (S>>(y*4+x)&1);
  //     cout << endl;
  //   }
  //   cout << endl;
  // }
  REP(S,1<<16) {
    set<char> st;
    REP(y,4) {
      REP(x,4) {
        if (S>>(y*4+x)&1) {
          st.insert(ba[y][x]);
        }
      }
    }
    ok[S] = (st.size() <= 1);
    // if (ok[S]) {
    //   REP(y,4) {
    //     REP(x,4)
    //       cout << (S>>(y*4+x)&1);
    //     cout << endl;
    //   }
    //   cout << endl;
    // }
  }
  queue<int> Q;
  Q.push((1<<16)-1);
  memset(dist,-1,sizeof(dist));
  dist[(1<<16)-1] = 0;
  while(!Q.empty()) {
    int S = Q.front(); Q.pop();
    if (S == 0) break;
    FOR(it, masks) {
      int t[3]={};
      if (ok[*it & S]) {
        int T = S & ~*it;
        if (dist[T] == -1) {
          dist[T] = dist[S] + 1;
          Q.push(T);
        }
      }
    }
  }
  cout << dist[0] << endl;
}

Measured memory_bytes: 1868
s = str(input())
lis = []
cnt = 0

while cnt < len(s):
    if cnt+1 < len(s) and (s[cnt] == "B" and s[cnt+1] == "C"):
        lis.append("D")
        cnt += 1
    else:
        lis.append(s[cnt])
    cnt += 1
  #    print(lis)

ans = 0
num = 0
for i in range(len(lis)):
    if lis[i] == "A":
        num += 1
    elif lis[i] == "D":
        ans += num
    else:
        num = 0
print(ans)

Measured memory_bytes: 5096
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;

int main()
{
  int a,b;
  cin >> b >> a;
  string fifty_dot = ".#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#";  
  string black_100 = "####################################################################################################";
  string white_100 = "....................................................................................................";
  a -= 1;
  b -= 1; 
  
  cout << 100 << " " << 100 << endl; 
  REP(i,25){
    if(b>50){
      b -= 50; 
      cout << fifty_dot << endl;
    }
    else if(b>0){
      int remain = 50-b;
      while(b>0){
        cout << "#.";
        b -= 1;
      }
      REP(i,remain*2){
        cout << "#";
      }
      cout << endl;
    }
    else{
      cout << black_100 << endl;
    }
    cout << black_100 << endl;
  }
 
  REP(i,25){
    cout << white_100 << endl;
    if(a>50){
      a -= 50; 
      cout << fifty_dot << endl;
    }
    else if(a>0){
      int remain = 50-a;
      while(a>0){
        cout << ".#";
        a -= 1;
      }
      REP(i,remain*2){
        cout << ".";
      }
      cout << endl;
    }
    else{
      cout << white_100 << endl;
    }
  }

  /*
       int i;
       cin >> i;
       */

    //cout << i/j << " " <<  i%j << " ";
    //cout << fixed << setprecision(5) << i/(double)j << endl;
}



Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <iostream>
#include <utility>
 
using namespace std;
using ll = long long;
using ld = long double;
using Vl = vector<ll>;
using pll = pair<ll, ll>;
using vb = vector<bool>;
using vs = vector<string>;

#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, m, n) for(int i = m; i < n; i++)

ll N;
Vl dp(3);
Vl a(N);
Vl b(N);
Vl c(N);

int main() {
    cin >> N;
    a.resize(N);
    b.resize(N);
    c.resize(N);
    REP(i,N) cin >> a[i] >> b[i] >> c[i];

    dp[0] = a[0];
    dp[1] = b[0];
    dp[2] = c[0];

    FOR(i,1,N){
        ll ba = dp[0];
        ll bb = dp[1];
        ll bc = dp[2];
        dp[0] = a[i] + max(bb,bc);
        dp[1] = b[i] + max(bc,ba);
        dp[2] = c[i] + max(ba,bb);
    }

    cout << max(dp[0], max(dp[1], dp[2]));
    return 0;
}

Measured memory_bytes: 2560