akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <map>
using namespace std;

typedef long long ll;

#define INF 10e10
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define MAX 100
#define MOD 1000000007
#define pb push_back

/* add vars here */

ll n,m;
typedef pair<ll, ll> lp;

/* add your algorithm here */

int main() {
  cin >> n >> m;
  map<ll, ll> mp;
  vector<lp> de;
  rep(i,m) {
    lp p;
    cin >> p.first >> p.second;
    if (p.first == 1) mp[p.second] = p.first;
    if (p.second == n) de.pb(p);
  }

  bool flag = false;
  for (auto itr : de) {
    if (mp[itr.first] == 1) {
      flag = true;
      break;
    }
  }

  if (flag) {
    cout << "POSSIBLE" << endl;
  } else {
    cout << "IMPOSSIBLE" << endl;
  }
}


Measured memory_bytes: 14320
#include <iostream>
#include <vector>
using ll = long long;
#define rep(i, n) for(ll i = 0; i < n; i++)
using namespace std;

const ll mod = 1000000007;

int main(){
  ll n;
  cin >> n;
  vector<ll> color(3, 0);
  ll a;
  ll ans = 1;
  rep(i, n){
    cin >> a;
    ll count = 0;
    rep(j, 3){
      if (a == color[j]){
        count++;
      }
    }
    ans = ans * count % mod;
    rep(j, 3){
      if (a == color[j]){
        color[j]++;
        break;
      }
    }
  }
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <cmath>
#include <cstdio>
#include <stack>
#include <queue>
#include <vector>
#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;

string s;

int main(){
    cin>>s;
    for(ll i=0;i<4;++i){
        cout<<s[i];
    }
    cout<<' ';
    for(ll i=4;i<12;++i){
        cout<<s[i];
    }
    cout<<endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long lint;
#define repi(i,a,b) for(lint i=(a), i##_len=(b); i<i##_len; ++i)
#define rep(i,n) repi(i,0,n)
#define all(x) (x).begin(),(x).end()
#define tsort(v) sort((v).begin(), (v).end())
#define trev(v) tsort(v); reverse((v).begin(), (v).end())
#define siz(v) ((int)(v).size())
#define ers(v, n) (v).erase((v).begin() + n)
#define cnt(v, n) count(all(v), n)
#define el "\n"
#define co(x) cout<<(x)<<el
#define coc(c, a, b) if(c)co((a));else co((b))
#define YES(c) coc(c,"YES", "NO")
#define Yes(c) coc(c,"Yes", "No")
#define yes(c) coc(c,"yes", "no")
#ifdef tqktmp_1
#define gc() getchar(); getchar()
#else
#define gc() 1
#endif

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

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

    string a,b,c;cin>>a>>b>>c;
    YES(a.back()==b[0]&&b.back()==c[0]);
}

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

using namespace std;

int main() {
    int n;

    cin >> n;

    vector<int> a(n);

    for(int i = 0; i < n; ++i) {
        cin >> a.at(i);
    }

    map<int, int> l, r;

    for(int i = 0; i < n; ++i) {
        l[i + a.at(i)]++;
        r[i - a.at(i)]++;
    }

    int_fast64_t c = 0;

    for(auto p: l) {
        c += static_cast<int_fast64_t>(p.second) * r[p.first];
    }

    printf("%ld\n", c);

    return 0;
}

Measured memory_bytes: 29816
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

typedef long long int ll;

using namespace std;

int main(void){

    int n, m;
    ll ans = 0;

    cin >> n >> m;

    priority_queue<pair<int, int>> data;

    for(int i = 0;i < n;i++){
        int x; cin >> x;
        data.push(make_pair(x, 1));
    }

    for(int i = 0;i < m;i++){
        int a, b;
        cin >> a >> b;
        data.push(make_pair(b, a));
    }

    for(int i = 0;i < n;i++){
        pair<int, int> p = data.top();
        data.pop();
        ans += p.first;
        if(p.second > 1){
            p.second--;
            data.push(p);
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 2420
#include<bits/stdc++.h>
/************************************************/
#define rep(i,n) for(int i=0;i<n;i++)
#define mp make_pair
#define pb push_back
#define fr first
#define se second
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define sz(s) s.size()
#define all(s) s.begin(),s.end()
#define zero(x) memset(x,0,sizeof(x))
#define vii vector<pair<int,int> >
#define mpis map<int,string>
#define mpii map<int,int>
#define mpsi map<string,int>
#define re return
/************************************************/
using namespace std;
int n,d,a[100000],mx,fr;
long long k(long long p,long long x,long long m){
	long long res=1;
	while(p)
	{
		if(p%2==1)
		{
			res=res*x%m;
		}
		p/=2;
		x=x*x%m; 
	}
	re res;
}
int main(){
	cin>>n;
	rep(i,n){
		cin>>d;
		a[d]++;
		if(i==0)
		fr=d;
		mx=max(mx,d);
	}
	if(a[0]!=1||fr!=0){
		cout<<0;
		re 0;
	}
	for(int i=1;i<=mx;i++)
	if(a[i]==0){
		cout<<0;
		re 0;
	}
	long long ans=1;
	for(int i=2;i<=mx;i++){
		long long ans1=k(a[i],a[i-1],998244353);
		ans*=ans1;
		ans%=998244353;
	}
	cout<<ans;
	re 0;
}

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

auto chmin = [](auto&& l, auto r) { return r < l ? l = r, 1 : 0; };

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  int res = 0, mn = n;
  while (n--) {
    int a;
    cin >> a;
    --a;
    res += chmin(mn, a);
  }
  cout << res << '\n';
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;//list用
using System.Text;//StringBuilder用
using System.Collections;
using System.Linq;
class Program
{
    static List<int> s = new List<int>();
    static decimal result;
static Hashtable ht=new Hashtable();
static StringBuilder sb = new StringBuilder();
static int N,M,K;
static long[,] table;
    static void Main()
    {
Read4();
      Read2();
      int[] check=new int[N];
      check[0]=0;
      for(int i=1;i<N;i++){
        int tmp=2000000000;
for(int j=1;j<=K;j++){
if(i-j<0){break;}
  tmp=Math.Min(check[i-j]+Math.Abs(s[i]-s[i-j]),tmp);
}
        check[i]=tmp;
      }
                    Console.WriteLine(check[N-1].ToString());

    }


    static void Read1()//1項
    {
        string tmp = Console.ReadLine();
        N = int.Parse(tmp);
    }
 
    static void Read2()//複数項（項目数Ｎ）
    {
        string[] tmp = Console.ReadLine().Split(' ');
        for (int i = 0; i < N; i++) { s.Add(int.Parse(tmp[i])); }
    }
    static void Read3()//1行複数項
   {
       string[] tmp = Console.ReadLine().Split(' ');
       for (int i = 0; i < tmp.Length; i++) { s.Add(int.Parse(tmp[i])); }
    }
    static void Read4()//NK１行
    {
        string[] tmp = Console.ReadLine().Split(' ');
       N = int.Parse(tmp[0]);
       K = int.Parse(tmp[1]);
    }
    static void Read5()//N行K項
    {

 
    }


}

Measured memory_bytes: 17504
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define MOD 1000000007
#define all(c) c.begin(), c.end()
#define rep(i, s, e) for (auto i = s; i < e; i++)
#define peek(c)      \
	for (auto i : c) \
		cout << i << ' ';

void solve()
{
	int n;
	cin >> n;
	int divs = 0, ones = 0;
	rep(i, 0, n)
	{
		int x;
		cin >> x;
		if (x % 2)
			ones++;
		if (x % 4 == 0)
			divs++;
	}
	if (divs == 0 && ones > 0)
		cout << "No";
	else if (divs + ones == n && ones <= divs + 1)
		cout << "Yes";
	else if (divs < ones)
		cout << "No";
	else
		cout << "Yes";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	solve();
	cerr << "\n\n~" << 500 * clock() / CLOCKS_PER_SEC << "ms\n";
	return 0;
}


Measured memory_bytes: 256
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left #bisect_left(list, value)
#from fractions import gcd
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N = int(input())

if N>999:
    print('ABD')
else:
    print('ABC')




Measured memory_bytes: 3316
N = int(input())
K = int(input())
X = int(input())
Y = int(input())
price = 0
if N <= K:
  for i in range(N):
    price += X
  print(price)
else:
  for i in range(K):
    price += X
  for i in range(N-K):
    price += Y
  print(price)

Measured memory_bytes: 9072
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dump(...)
#endif
#define endl "\n"
#define ll long long
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define RREP(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (int i = ((int)(x)); i > 0; i--)
#define INF 2147483647
#define LLINF 9223372036854775807LL
#define vi vector<int>
#define vvi vector<vector<int>>
#define pi pair<int, int>
#define ALL(a) (a).begin(), (a).end()
#define BIT(n) (1LL << (n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()) //sortしてからつかうこと
constexpr ll MOD = 1e9 + 7;
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
ll A, B, C, D, E, F, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;
ll ans = 0;

template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (T &x : vec)
        is >> x;
    return is;
}

int intceil(int a, int b) {
    return (a + (b - 1)) / b;
}

signed main() {
    cin >> N;
    vi p(N);
    cin >> p;
    REP(i, N) {
        if (p[i] == i + 1) {
            p[i] = 1;
        } else
            p[i] = 0;
    }
    REP(i, N - 1) {
        if (p[i] > 0 && p[i + 1] > 0) {
            p[i + 1] = p[i] + 1;
            p[i] = 0;
        }
    }
    dump(p);
    REP(i, N) {
        ans += intceil(p[i], 2);
    }

    cout << ans << endl;
}

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

using namespace std;

int main()
{
   long int n;
   scanf("%ld",&n);
   
   int sum=0;
     long int o=n;
   while(n!=0)
   {
     sum+=n%10;
     n/=10;
   }
  
  if(o%sum==0)
      printf("Yes");
  
  else
     printf("No");
}

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

int main()
{
	while (true) {
		int N, A, B, C, X;

		cin >> N >> A >> B >> C >> X;

		if (N == 0 && A == 0 && B == 0 && C == 0 && X == 0) {
			break;
		}

		vector<int> frames;

		for (int i = 0; i < N; i++) {
			int temp;
			cin >> temp;
			frames.push_back(temp);
		}

		int ans = -1;
		int cur = 0;

		if (X == frames[cur]) {
			cur++;
			if (N == 1) {
				ans = 0;
			}
		}
		if (N != cur) {
			for (int i = 1; i <= 10000; i++) {
				X = (A*X + B) % C;

				if (X == frames[cur]) {
					cur++;
					if (cur == N) {
						ans = i;
						break;
					}
				}
			}
		}

		cout << ans << endl;
	}
}

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

#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define ll long long int
#define mod 1000000007

int h,w,m;

void solve()
{
    cin>>h>>w>>m;
    map<int,int> rfreq,cfreq;
    set<pair<int,int>>targets;
    int a,b;
    while(m--)
    {
        cin>>a>>b;
        rfreq[a]++;
        cfreq[b]++;
        targets.insert({a,b});
    }
    vector<int>rows;
    vector<int>cols;
    int count = 0;
    int row = 0,col=0;
    for(auto i: rfreq)
    {
        if(i.second>count)
        {
            count = i.second;
            
        }
    }
    int ccount=0;
    for(auto i: cfreq)
    {
        if(i.second>ccount)
        {
            ccount = i.second;
        }
    }
    for(auto i: rfreq)
    {
        if(i.second==count)
        {
            rows.push_back(i.first);
        }
    }
    for(auto i: cfreq)
    {
        if(i.second==ccount)
        {
            cols.push_back(i.first);
        }
    }
    
    for(int i=0;i<rows.size();i++)
    {
        for(int j=0;j<cols.size();j++)
        {
            if(targets.find({rows[i],cols[j]})==targets.end())
            {
                cout<<count+ccount;
                return;
            }
        }
    }
    cout<<count+ccount-1;
}

int main()
{
    sync;
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
        cout<<"\n";
    }
    return 0;
}







Measured memory_bytes: 49604
#include<iostream>

using namespace std;

int main()
{int A,B,K; cin >> A >> B >> K;
 if ( A + K - 1 < B - K + 1){
 for(int i = 0; i < K; i++){
   cout << A + i << endl;}
 for(int j = K - 1; j >= 0 ; j--){
     cout << B - j << endl;}}
 else{ 
   for(int i = A; i <= B; i++){ cout << i << endl;}}
 
     
     return 0;}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int,int> P;
#define S second
#define F first
#define INF (1000000000)
int N,K;
struct edge{
  int to,cost;
  edge(){}
  edge(int to,int cost){ this->to = to; this->cost = cost; }
};
vector<edge> G[102];
int dijk(int a,int b){
  int h[102];
  for(int i=0;i<102;i++) h[i]=INF;
  priority_queue<P,vector<P>,greater<P> > q;
  while(!q.empty()) q.pop();
  h[a]=0;
  q.push( P(0,a) );
  while(!q.empty()){
    P p = q.top(); q.pop();
    // printf("%d %d\n",p.F,p.S);
    for(int i=0;i<(int)G[p.S].size();i++){
      edge e = G[p.S][i];
      //      printf("e %d %d + %d\n",h[e.to],e.cost,p.F);
      if( h[e.to] > e.cost + p.F ){
	h[e.to] = e.cost + p.F;
	q.push( P(e.cost + p.F, e.to) );
      }
    }
  }
  if(h[b]==INF) return -1;
  else return h[b];
}
int main(){
  while(1){
    scanf("%d %d",&N,&K);
    if(!N && !K) break;
    for(int i=0;i<K;i++){
      int cd;
      scanf("%d",&cd);
      if(!cd){
	int a,b;
	scanf("%d %d",&a,&b);
	printf("%d\n",dijk(a,b));
      } else{
	int c,d,e;
	scanf("%d %d %d",&c,&d,&e);
	G[c].push_back( edge(d,e) );
	G[d].push_back( edge(c,e) );
      }
    }
    for(int i=0;i<=N;i++) G[i].clear();
  }
}

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    ll N;
    cin >> N;
    vector<ll> D(N);
    ll ans = 0;
    rep(i, N) cin >> D[i];
    rep(i, N - 1) {
        rep2(j, i + 1, N) {
            ans += D[i] * D[j];
        }
    }
    cout << ans << endl;
    return 0;
}


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

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

Node *root, *NIL;

void insert(int k) {
    Node *y = NIL;
    Node *x = root;
    Node *z;
    
    z = (Node *)malloc(sizeof(Node));
    z->key   = k;
    z->left  = NIL;
    z->right = NIL;
    
    while(x != NIL) {
        y = x;
        if(z->key < x->key) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    
    z->parent = y;
    if(y == NIL) {
        root = z;
    } else {
        if( z->key < y->key) {
            y->left = z;
        } else {
            y->right = z;
        }
    }
}

void inorder(Node *u) {
    if(u == NIL) return;
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
}
void preorder(Node *u) {
    if(u == NIL) return;
    printf(" %d",u->key);
    preorder(u->left);
    preorder(u->right);
}
    
int main(void) {
    int n, i, x;
    char com[16];
    scanf("%d",&n);
    
    for(i=0;i<n;i++) {
        scanf("%s",com);
        if(!strcmp(com,"insert")) {
            scanf("%d",&x);
            insert(x);
        } else if(!strcmp(com,"print")) {
            inorder(root);
            printf("\n");
            preorder(root);
            printf("\n");
        }
    }

    return 0;
}

/*
8
insert 30
insert 88
insert 12
insert 1
insert 20
insert 17
insert 25
print
*/


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

using namespace std;

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

typedef long long ll; typedef vector<int> VI; typedef pair<ll,int> pii;
const ll mod = 1e9+7;


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

	int n;
	string s;
	cin >>n >> s;
	auto os =s;
	
	int ct=0;
	string s2;
	for(bool nxt=true; nxt;){
		nxt = false;
		n = sz(s);
		rep(i,n-1) if(s[i]=='(' && s[i+1]==')'){ s[i]=s[i+1]='#'; nxt=true;}
		s2 = "";
		rep(i,n) if(s[i] !='#') s2 += s[i];
		s = s2;
	}
	n = sz(s);
	//cout <<s <<"##\n";
	
	int bf=0, af=0;
	for(auto x: s){
		if(x==')') bf++;
		if(x=='(') af++;
	}
	//printf("ba=%d:%d:%d\n",bf, af, n);
	string ans;
	if(bf>0) ans += string(bf, '(');
	ans += os;
	if(af>0) ans += string(af, ')');
	cout << ans <<"\n";
	return 0;
}




Measured memory_bytes: 256
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    c = [-1]
    INF = 10**9+7
    for _ in range(N):
        a = int(input())
        if c[-1] == a-1:
            continue
        c.append(a-1)
    
    c.pop(0)
    d,M = len(c),max(c)
    dp = [1 for _ in range(d+1)]
    c_dp = [0 for _ in range(M+1)]
    for i in range(d):
        now = c[i]
        dp[i+1] = (dp[i] + c_dp[now])%INF
        c_dp[now] = dp[i+1]
                
    print(dp[-1])
    
if __name__ == "__main__":
    main()


Measured memory_bytes: 20416
/*------------------------------------
........Bismillahir Rahmanir Rahim....
..........created by Abdul Aziz.......
------------------------------------*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#define   mod  998244353
#define   int  long long 
#define   ld   long double
#define   pb   push_back
#define   vi  vector<int> 
#define   dbg(x)  cerr << #x << " = " << x << '\n'
#define   sz(x)  (int)x.size()
#define   ff   first
#define   ss   second
#define   pii  pair<int,int>
using namespace std;

inline void solve(){
    int n,m,k; cin>>n>>m>>k; 
    vi  a(n+1,0),b(m+1,0);
    int ans=0;
    for (int i=1;i<=n;i++){
        cin >> a[i] ;
        a[i] += a[i-1];
    }
    for (int i=1;i<=m;i++){
        cin >> b[i] ;
        b[i] += b[i-1];
    }
    for (int i=0,j=m;i<=n and j>=0;i++){
        if (a[i]>k) break;
        while (a[i]+b[j]>k) j--;
        ans = max(ans,i+j);
    }
    cout << ans << endl;
}

signed main()
{
    int n=1; // cin>>n;
    while (n--) solve();
    return 0;
}


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

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

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

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

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

N = getN()
logk = N.bit_length()

# 一般項が出ない場合でも
# 漸化式にできるなら行列計算に落とし込める
dp = [[[0, 0, 0, 0] for i in range(4)] for i in range(logk)]
dp[0] = [[8, 1, 1, 0], [0, 9, 0, 1], [0, 0, 9, 1], [0, 0, 0, 10]]

# 行列掛け算 O(n3)かかる
def array_cnt(ar1, ar2):
    h = len(ar1)
    w = len(ar2[0])
    row = ar1
    col = []
    for j in range(w):
        opt = []
        for i in range(len(ar2)):
            opt.append(ar2[i][j])
        col.append(opt)

    res = [[[0, 0] for i in range(w)] for i in range(h)]
    for i in range(h):
        for j in range(w):
            cnt = 0
            for x, y in zip(row[i], col[j]):
                cnt += x * y
            res[i][j] = cnt
            res[i][j] %= mod
    return res

for i in range(1, logk):
    dp[i] = array_cnt(dp[i - 1], dp[i - 1])

ans = [[1, 0, 0, 0]]
for i in range(logk):
    if N & (1 << i):
        ans = array_cnt(ans, dp[i])
        
print(ans[0][-1] % mod)

Measured memory_bytes: 83784
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
using namespace std;
//
//
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define int long long
#define ll long long
#define ld long double
#define gap ' '
#define endl '\n'

void solve() {
	int n;
	cin>>n;
	vector<int> h(n+1);
	for(int i=1;i<=n;i++) cin>>h[i];
	int dp[n+1];
	dp[1]=0;
	for(int i=2;i<=n;i++) {
		dp[i]=1e10;
		if(i-1>=1) dp[i]=min(dp[i],dp[i-1]+abs(h[i-1]-h[i]));
		if(i-2>=1) dp[i]=min(dp[i],dp[i-2]+abs(h[i]-h[i-2]));
	}
	cout<<dp[n]<<endl;
}
void solve(bool testcase) {
	int t;cin>>t;while(t--)solve();
}
int32_t main() {
	fio
	solve();
	return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<cstdio>
#include<cstdlib>
using namespace std;

struct node{
    int key;
    node *right,*left,*parent;
};
node *root,*nil;

void insert(int k){
    node *y=nil;
    node *x=root;
    node *z;
    
    z=(node *)malloc(sizeof(node));
    z->key =k;
    z->left = nil;
    z->right = nil;
    
    while(x!=nil){
        y=x;
        if(z->key < x->key){
            x= x->left;
        }else{
            x = x->right;
        }
    }
    z->parent =y;
    if(y==nil){
        root=z;
    }else{
        if(z->key<y->key){
            y->left=z;
        }else{
            y->right=z;
        }
    }
}

void inorder(node *u){
    if(u==nil)return;
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
}

void preorder(node *u){
    if(u==nil)return;
    printf(" %d",u->key);
    preorder(u->left);
    preorder(u->right);
}
int main(){
    int n,x;
    string  com;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>com;
        if(com=="insert"){
            cin>>x;
            insert(x);
        }else if(com=="print"){
            inorder(root);
            cout<<endl;
            preorder(root);
            cout<<endl;
        }
    }
    return 0;
    
}



Measured memory_bytes: 26688
#include <iostream>
#include <vector>
 
#define FOR(i, a, b) for(int (i) = (a); (i) < (b); ++(i))
#define REP(i, n) FOR(i, 0, n)

constexpr int MAX_SIZE = 1e5 + 1;
std::vector<int> A, B;
std::vector<int> Count(MAX_SIZE, 0);

int main(void){
    int n, m; scanf("%d%d", &n, &m);
    A.resize(m, 0);
    REP(i, n) {
        int a; scanf("%d", &a);
        A[a % m]++;
        Count[a]++;
    }
    B.resize(m, 0);
    REP(x, MAX_SIZE) B[x % m] += (Count[x] >> 1);
    // x個あって, aペア作れる <~> y個あって, bペア作れる

    int cnt = 0;
    REP(i, m){
        int j = (m - i) % m;
        if(j < i) break;
        if(i == j) {cnt += A[i] / 2; continue;}
        int p = std::min(A[i], A[j]);
        cnt += p; A[i] -= p; A[j] -= p;
        int q1 = std::min(A[i] / 2, B[i]);
        int q2 = std::min(A[j] / 2, B[j]);
        cnt += q1 + q2;
    }
    printf("%d\n", cnt);
    

    return 0;
}


Measured memory_bytes: 1408
n, q = map(int, input().split(" "))

tree = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split(" "))
  tree[a-1].append(b)

ans = [0 for _ in range(n)]
for _ in range(q):
  p, x = map(int, input().split(" "))
  ans[p-1] += x
  
for i, c in enumerate(ans):
    for j in tree[i]:
        ans[j-1] += c

print( *ans )

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

int main()
{
  string str;
  cin >> str;
  char s = 'a';
 
  for(int i=s; i<s+26; i++){
    for(int j=0; j<str.size(); j++){
      if(count(str.begin(), str.end(), i) >= 2){
	cout << "no" << endl; return 0;
      }
    }
  }
  cout << "yes" << endl;
}


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

using namespace std;

using ll = long long;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
char ch[4] = {'R', 'L', 'U', 'D'};

int main(){
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cout.setf(ios::fixed); cout.precision(17);
  int n;
  cin >> n;
  vector<long long> x(n), y(n);
  for(int i = 0; i < n; i++){
    cin >> x[i] >> y[i];
  }
  for(int i = 1; i < n; i++){
    if(((x[0] + y[0]) & 1) != ((x[i] + y[i]) & 1)){
      cout << "-1\n";
      return 0;
    }
  }
  vector<long long> moves;
  for(int i = 30; i >= 0; i--){
    moves.push_back((1<<i));
  }
  if((x[0] + y[0]) % 2 == 0){ // same parity throws an even lenght, so add +1 to 1,2,4,...
    moves.push_back(1);
  }
  cout << moves.size() << "\n";
  for(int i = 0; i < moves.size(); i++){
    cout << moves[i] << " ";
  } cout << "\n";
  for(int i = 0; i < n; i++){
    string seq = "";
    ll xx = 0, yy = 0;
    for(int k = 0; k < moves.size(); k++){
      ll _min = 1e11;
      int at = -1;
      for(int j = 0; j < 4; j++){
        ll dist = abs( moves[k] * dx[j] - x[i]) + abs( moves[k]* dy[j] - y[i]);
        if(dist < _min){
          _min = dist;
          at = j;
        }
      }
      seq += ch[at];
      xx += moves[k] * dx[at];
      yy += moves[k] * dy[at];
      x[i] -= moves[k] * dx[at];  // now the origin is at (moves[at]*dx[at], moves[at]*dy[at])
      y[i] -= moves[k] * dy[at];  // i.e. (-4,0), so x and y must shifft.
    }
    //cout << xx << " " << yy << "\n";
    cout << seq << "\n";
  }
  return 0;
}


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

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rept(i,n) for(int (i)=0;(i)<=(int)(n);(i)++)
#define reps(i,s,n) for(int (i)=(s);(i)<(int)(n);(i)++)
#define repst(i,s,n) for(int (i)=(s);(i)<=(int)(n);(i)++)
#define repr(i,n) for(int (i)=(n);(i)>=0;(i)--)
#define each(itr,v) for(auto (itr):(v))
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln "\n"
#define show(x) cout << #x << " = " << x ln
#define dbg(x) cout<<#x"="<<x ln

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

const int inf = (int)1e9;
const ll linf = (ll)1e18;
const int mod = (int)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ━━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…
// .｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋
// ・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・

ll p = 1, n;

int main() {
	cin >> n;
	repst(i,2,n) p = (p*i)%mod;
	cout << p << ln;
}

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

#define INF 1234567890
#define ll long long

int N, K;
ll A[200201];

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	ll money = 1000, cnt = 0;
	for(int i=1; i<=N; i++)
		cin >> A[i];
	for(int i=1; i<=N-1; i++)
	{
		if (A[i] < A[i+1])
		{
			cnt += money / A[i];
			money %= A[i];
		}
		else if (A[i] > A[i+1])
		{
			money += cnt * A[i];
			cnt = 0;
		}
	}
	money += cnt * A[N];
	cnt = 0;
	cout << money;
	return 0;
}

Measured memory_bytes: 3652
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)

int gcd(int x, int y)
{
    if(x < y)   swap(x, y);
    if(y == 0)  return x;

    return gcd(x % y, y);
}

int main()
{
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, N)   cin >> A[i];
    vector<int> L(N), R(N);
    rep(i, N){
        L[i] = R[i] = A[i];
    }
    for(int i = 1; i < N; i++){
        L[i] = gcd(L[i-1], L[i]);
        R[N-i-1] = gcd(R[N-i-1], R[N-i]);
    }
    int ans = 0;
    for(int i = 0; i < N; i++){
        if(i == 0){
            ans = max(ans, R[i+1]);
            continue;
        }
        if(i == N-1){
            ans = max(ans, L[i-1]);
            continue;
        }
        ans = max(ans, gcd(L[i-1], R[i+1]));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;

int main() {
    int n, k;
    double win = 0;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        int temp = i;
        while (temp < k) {
            temp *= 2;
            cnt++;
        }
        win += 1.0 / pow(2, cnt);
    }
    cout << setprecision(15) << win / n << endl;
    return 0;
}

Measured memory_bytes: 4132
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;


namespace 競プロCS {
    class ABC159A {
        static void Main() {
            int[] nums = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            Console.WriteLine(Calc(nums[0]) + Calc(nums[1]));

        }

        static int Calc(int n) {
            int total = 0;
            for (int i = 1; i < n; i++) {
                total += i;
            }
            return total;
        }
    }
}


Measured memory_bytes: 13268
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>


using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD (ll)1000000007
#define P pair<ll, ll>

ll n;
vector<P> s;
int main() {
	cin >> n;
	REP(i, n) {
		ll a;
		cin >> a;
		s.push_back(P(a, i + 1));
	}
	sort(ALL(s));
	REP(i, n) {
		if (i != 0)cout << " ";
		cout << s[i].second;
	}
	cout << endl;
}

Measured memory_bytes: 2544
import java.util.*;

public class Main {
    public static void main(String args[] ) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int k = sc.nextInt();

        int div = 1;
        for (int i = Math.min(a, b); i >= 0; i--) {
            if (a % i == 0 && b % i == 0 && --k == 0) {
                div = i;
                break;
            }
        }

        System.out.println(div);
    }
}

Measured memory_bytes: 22996
#include <bits/stdc++.h>
typedef long long int LL;
typedef unsigned long long int ULL;
using namespace std;

// 插入此處

int h[300005], w[300005];
int hc[300005], wc[300005];

int main() {
    int H, W, M;
    cin >> H >> W >> M;
    for (int i = 0; i < M; i++) {
        cin >> h[i] >> w[i];
        hc[h[i]]++;
        wc[w[i]]++;
    }
    int max_h = 0, max_w = 0;
    for (int i = 1; i <= H; i++) {
        max_h = max(max_h, hc[i]);
    }
    for (int i = 1; i <= W; i++) {
        max_w = max(max_w, wc[i]);
    }
    LL same_h = 0, same_w = 0;
    for (int i = 1; i <= H; i++) {
        if (hc[i] == max_h) { same_h++; }
    }
    for (int i = 1; i <= W; i++) {
        if (wc[i] == max_w) { same_w++; }
    }
    LL same = 0;
    for (int i = 0; i < M; i++) {
        if (hc[h[i]] == max_h && wc[w[i]] == max_w) {
            same++;
        }
    }
    if (same == same_h * same_w) {
        cout << max_h + max_w - 1 << endl;
    } else {
        cout << max_h + max_w << endl;
    }
}


Measured memory_bytes: 8272
#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
long long dp[100005][2];
int main()
{
    char s[100005];
    cin>>s+1;
    dp[0][1]=1;
    dp[0][0]=0;
    int n=strlen(s+1);
    for(int i=1;s[i];i++)
    {
        dp[i][0]=(dp[i-1][0]*3)%mod;
        if(s[i]=='1')
        {
            dp[i][1]=(dp[i-1][1]*2)%mod;
            dp[i][0]+=dp[i-1][1];
            dp[i][0]=(dp[i][0])%mod;
        }
        else
        {
            dp[i][1]=dp[i-1][1];
        }
    }
    printf("%lld\n",(dp[n][1]+dp[n][0])%mod);
}


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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for (int i = a; i < (int)b; ++i)
#define rrep(i, n) for (int i = ((int)n - 1); i >= 0; --i)

using ll = long long;
using ld = long double;

const ll INF = 1e18;
const int Inf = 1e9;
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<ll> a(n);
    rep (i, n) cin >> a[i];
    sort(a.begin(), a.end());
    vector<bool> check(a[n - 1] + 10);
    vector<int> cnt(a[n - 1] + 10);
    int res = 0;
    rep (i, n) {
        cnt[a[i]]++;
        for (int j = a[i] * 2; j < a[n - 1] + 10; j += a[i]) check[j] = true;
    }
    rep (i, n) {
        if (!check[a[i]] && cnt[a[i]] == 1) res++;
    }
    cout << res << endl;
    
    return 0;
}



Measured memory_bytes: 8632
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
int main(){
    int n,k;
    double win_p = 0;
    cin >> n >> k;
    for(int i = 1;i <= n;i++){
        int e = 0;
        while(i*pow(2.0,e) < k){
            e++;
        }
        win_p += (1.0/n) * pow((1.0/2),e);
    }
    cout << std::setprecision(12) << win_p << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
	string s;
	cin>>s;
	if(s.size()<=3){
		cout<<s<<endl;
		return 0;
	}
	for(int i=0;i<3;i++){
		cout<<s[i];
	}
	cout<<endl;
	return 0;
}

Measured memory_bytes: 3036
#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    int a[100005];
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    int current_botan = 1;
    int ans = 0;
    for(int i=0; i<n; i++){
        if(current_botan == 2){
            cout << ans << endl;
            return 0;
        }
        current_botan = a[current_botan];
        ans++;
        }
        cout << -1 << endl;
}

Measured memory_bytes: 640
#include <cassert>

#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
//#include <boost/foreach.hpp>
//#include <boost/range/algorithm.hpp>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define ll long long
#define Sort(v) sort(all(v))
#define INF 1000000000
#define END return 0
#define pb push_back
#define se second
#define fi first
#define pb push_back
#define all(v) (v).begin() , (v).end()
#define MP make_pair
#define MOD 1000000007LL
using namespace std;
int day[12]={31,28,31,30,31,30,31,31,30,31,30,31};

struct P{
    int x,y;
};

int main (){
    int n;
    cin>>n;
    vector<int> v(n);
    rep(i,0,n)cin>>v[i];
    sort(all(v));
    cout<<v[v.size()-1]/2+accumulate(v.begin(),v.end()-1,0)<<endl;
}


/*
5 5
2...2
.....
..1..
.....
2...2

5 10
..3.......
.....1....
..........
....3.....
..........



1010
00000
00000
00000
00000
*/


Measured memory_bytes: 256
N, M, X = map(int, input().split())
A = list(map(int, input().split()))

cost_a, cost_b = 0, 0

for i in range(X, N):
    if i in A:
        cost_a += 1
for i in range(0, X):
    if i in A:
        cost_b += 1
print(min(cost_b, cost_a))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-11;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int main(){
	while(1){
		int n;
		cin>>n;
		if(n==0) break;
		vvi a(n,vi(n+1));
		int N=1<<n;
		vi dp(N,inf);
		dp[0]=0;
		for(int i=0;i<n;i++) for(int j=0;j<=n;j++) cin>>a[i][j];
		for(int i=0;i<N-1;i++){
			for(int j=0;j<n;j++) if(!(i&1<<j)){
				int mn=a[j][0];
				for(int k=0;k<n;k++) if(i&1<<k) mn=min(mn,a[j][k+1]);
				dp[i+(1<<j)]=min(dp[i+(1<<j)],dp[i]+mn);
			}
		}
		cout<<dp.back()<<endl;
	}
}


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


bool condition( int *index, int *A, int right ){
    bool condition = true;

    for( int j = 0; j < 21; j++ ){
        if( A[right] & ( 1 << j ) ) index[j]++; //立っているbitを足す
    }

    for( int i = 0; i < 21; i++ ){ // 条件(各bitが1以下か)をcheck
        if( index[i] > 1 ) condition = false; 
    }

    for( int j = 0; j < 21; j++ ){
        if( A[right] & ( 1 << j ) ) index[j]--; //立っているbitを足す
    }

    return condition;
}

int main(){

    int N, A[200000];
    cin >> N;
    for( int i = 0; i < N; i++ ) cin >> A[i];


    long ans = 0; 
    int right = 0;
    int index[21] = {};
    
    // しゃくとり法
    for( int left = 0; left < N; left++ ){ // 左端を動かす
        while( condition( index, A, right ) && right < N ){ // [left,right)の範囲が条件を満たす間
            for( int j = 0; j < 21; j++ ){
                if( A[right] & ( 1 << j ) ) index[j]++; //立っているbitを足す
            }
            right++;
            //cout << left << " " << right << endl;
        }

        ans += right - left; // その区間に含まれる全てが条件を満たす

        // iを1つ左へ動かすのでその分をbitから引く
        if( left == right ) right++;
        else{
            for( int j = 0; j < 21; j++ ){
                if( A[left] & ( 1 << j ) ) index[j]--;
            }
        }
    }
    
    cout << ans << endl;

    return 0;

}

Measured memory_bytes: 1024
import java.util.*;
public class Main {
	int[][] dp = new int[10][10];
	
	void small(int x, int y) {
		dp[x][y]++;
		if(x + 1 < 10) {
			dp[x + 1][y]++;
			
		}
		if(y + 1 < 10) {
			dp[x][y + 1]++;
			
		}
		if(x - 1 >= 0) {
			dp[x - 1][y]++;
			
		}
		if(y - 1 >= 0) {
			dp[x][y - 1]++;
			
		}
	}
	
	void medium(int x, int y) {
		small(x, y);
		if(x + 1 < 10 && y + 1 < 10) {
			dp[x + 1][y + 1]++;
			
		}
		if(x - 1 >= 0 && y + 1 < 10) {
			dp[x - 1][y + 1]++;
			
		}
		if(x + 1 < 10 && y - 1 >= 0) {
			dp[x + 1][y - 1]++;
			
		}
		if(x - 1 >= 0 && y - 1 >= 0) {
			dp[x - 1][y - 1]++;
			
		}
	}
	
	void large(int x, int y) {
		medium(x, y);
		if(x + 2 < 10) {
			dp[x + 2][y]++;
			
		}
		if(y + 2 < 10) {
			dp[x][y + 2]++;
			
		}
		if(x - 2 >= 0) {
			dp[x - 2][y]++;
			
		}
		if(y - 2 >= 0) {
			dp[x][y - 2]++;
			
		}
	}
	
	void doIt() {
		Scanner stdIn = new Scanner(System.in);
		int max = Integer.MIN_VALUE;
		int count = 0;
		while(stdIn.hasNext()) {
			String input = stdIn.next();
			int x = input.charAt(0) - '0';
			int y = input.charAt(2) - '0';
			int mode = input.charAt(4) - '0';
			switch(mode) {
			case 1: small(x, y); break;
			case 2: medium(x, y); break;
			case 3: large(x, y); break;
			}
		}
		for(int r = 0; r < 10; r++) {
			for(int c = 0; c < 10; c++) {
				if(dp[r][c] != 0) {
					max = Math.max(max, dp[r][c]);
					continue;
				}
				count++;
			}
		}
		System.out.println(count + "\n" + max);
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new Main().doIt();
	}

}

Measured memory_bytes: 17144
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		if (a * b % 2 == 0) {
			System.out.println("Even");
		} else {
			System.out.println("Odd");
		}
	}
}


Measured memory_bytes: 21844
#include<stdio.h>
#include<string.h>
int main()
{
	char s[10];
	scanf("%s",s);
	if(strcmp(s,"SAT")==0)
	{
		printf("1\n");
	//	printf("It is Saturday today, and tomorrow will be Sunday.\n");
	}
	if(strcmp(s,"SUN")==0) 
	{
		printf("7\n");
	//	printf("It is Sunday today, and seven days later, it will be Sunday again.\n");
	}
	if(strcmp(s,"MON")==0) 
	{
		printf("6\n");
	//	printf("It is Monday today, and six days later, it will be Sunday again.\n");
	}
	if(strcmp(s,"TUE")==0) 
	{
		printf("5\n");
	//	printf("It is Tuesday today, and five days later, it will be Sunday again.\n");
	}
	if(strcmp(s,"WED")==0) 
	{
		printf("4\n");
	//	printf("It is Wednesday today, and four days later, it will be Sunday again.\n");
	}
	if(strcmp(s,"THU")==0) 
	{
		printf("3\n");
	//	printf("It is Thursday today, and three days later, it will be Sunday again.\n");
	}
	if(strcmp(s,"FRI")==0) 
	{
		printf("2\n");
	//	printf("It is Friday today, and two days later, it will be Sunday again.\n");
	}
	return 0;
} 

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

int main(){
    int N;
    cin >> N;
    int p[N];
    for(int i = 0; i < N; i++){
        cin >> p[i];
    }

    int ans = 0;
    for(int i = 1; i < N - 1; i++){
        if(p[i-1] < p[i] && p[i] <= p[i+1]){
            ans++;
        }else if(p[i-1] >= p[i] && p[i] > p[i+1]){
            ans++;
        }
    }
    cout << ans << endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define lli long long int
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define se second;
#define fi first;
#define endl '\n';
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define REP(i,n) for (int i = 1; i <= n; i++)
template<typename T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<typename T> void chmin(T& a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T& a, T b) { if (a < b) a = b; }
typedef long long ll;
typedef vector<vector<ll> > matrix;
const ll MOD = 1000000007;
const int K = 9;
const lli mod = 1e9 + 7;
const lli INF = 1e9 + 7;
const lli N=2*1e5;
lli visit[400001];
map<lli,vector<lli> >g;
map<string,lli>pi,m1,m2;
lli var1,var2,var3,var4,var5,var6;
vector<lli>v,v1,v2,v3,v4;
lli X[10][10];
string a,b;
lli n,m,l,t,r,q,p,k,x,y;
lli ans=0,ans1=0,ans2=0,ans3=0;
lli dp[N],cp[N][5];
int main(){
  _
  cin>>n>>k;
  for(lli i=0;i<n;i++){
    cin>>x;
    v.pb(x);
    dp[i]=INT_MAX;
  }
  dp[0]=0;
  dp[1]=abs(v[0]-v[1]);
  for(lli i=2;i<n;i++){
    for(lli j=1;j<=k;j++){
      if(j<=i){
        dp[i]=min(dp[i],dp[i-j]+abs(v[i]-v[i-j]));
      }
    }
  }
  cout<<dp[n-1]<<endl;
}


Measured memory_bytes: 5496
//Radhe Radhe
#include<bits/stdc++.h>
#define ll long long
#define fixed cout.setf(ios::fixed);
#define Precise cout.precision(7);
using namespace std;
int main()
{
    ll n,i;
    string s;
    cin>>n>>s;
    for(i=0;s[i];i++)
    {
    ll x=s[i]-'A';
    x+=n;
    x%=26;
    s[i]=x+'A';
    }
    cout<<s<<endl;


    return 0;
}





Measured memory_bytes: 3660
s=list(input())
n=len(s)
dp=[0]*(n+1)
dp[0]=0
dp[1]=1
if n>=2:
  dp[2]=1+(1 if s[0]!=s[1] else 0)
  for i in range(2,n):
    if s[i]!=s[i-1]:
      dp[i+1]=dp[i]+1
    else:
      dp[i+1]=dp[i-2]+2
print(dp[n])

Measured memory_bytes: 12612
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n, q;
        int[] T, S;
        int i, j, count = 0;
        n = cin.nextInt();
        T = new int[n + 1];
        for (i = 0; i < n; i++)
            T[i] = cin.nextInt();
        q = cin.nextInt();
        S = new int[q + 1];
        for (i = 0; i < q; i++)
            S[i] = cin.nextInt();
        for (i = 0; i < q; i++) {
            T[n] = S[i];
            for (j = 0; T[j] != S[i]; j++);
            if (j != n)
                count++;
        }
        System.out.println(count);
    }
}


Measured memory_bytes: 39900
import math as ma
a,b,h,m = map(int,input().split())
ans = abs(30 * (h%12) + 0.5 * m  - 6 * m)
if ans > 180:
    ans = abs(360 - ans)
c = ma.cos(ma.radians(ans))
res=(a**2)+(b**2)-((2*a*b)*c)
print(res**0.5)

Measured memory_bytes: 62404