akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0;i<(n);++i)
#define per(i, n) for(int i=(n)-1;i>=0;--i)
#define repa(i, n) for(int i=1;i<(n);++i)
#define foreach(i, n) for(auto &i:(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
using namespace std;
using ll = long long;
const ll MOD = (ll)1e9+7;
//const ll MOD = 998244353;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
using namespace std;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}

#ifdef DEBUG
#define OUTPUT(x) (output(x), outendl())
#else
#define OUTPUT(x) (void)0
#endif

ll modpow(ll x, ll b){
	ll res = 1;
	while(b){
		if(b&1)res = res * x % MOD;
		x = x * x % MOD;
		b>>=1;
	}
	return res;
}

ll modinv(ll x){
	return modpow(x, MOD-2);
}

bool was_output = false;
template<class t>
void output(t a){
	if(was_output)cout << " ";
	cout << a;
	was_output = true;
}
void outendl(){
	was_output = false;
	cout << endl;
}

int main(){
	ll t1, t2, a1, a2, b1, b2;
	cin >> t1 >> t2 >> a1 >> a2 >> b1 >> b2;
	a1 *= t1;
	b1 *= t1;
	a2 *= t2;
	b2 *= t2;
	if(a1+a2==b1+b2){
		cout << "infinity" << endl;
		return 0;
	}
	if((a1<b1)!=(a1+a2>b1+b2)){
		cout << 0 << endl;
		return 0;
	}

	ll maxs = abs(a1 - b1);
	ll d = abs(a1-b1+a2-b2);
	OUTPUT(a1);
	OUTPUT(a2);
	OUTPUT(b1);
	OUTPUT(b2);

	cout << maxs / d * 2 + (maxs%d!=0) << endl;
}


Measured memory_bytes: 256
def main():
    from sys import stdin, setrecursionlimit
    #from sys import stdin, setrecursionlimit
    #setrecursionlimit(10**9)
    #n = int(stdin.readline()[:-1])   
    #r = stdin.readline()[:-1]
    #r = [stdin.readline() for i in range(n)]
    #t = [int(stdin.readline()) for i in range(n)]
    #n = int(r)
    #a = r.split()
    #a,b,c = r.split()
    #a = list(map(int, r.split()))
    #a,b,c,d = map(int, r.split())
    #a = list(map(int, r.split()))
    #a = [int(s[i]) for i in range(1, n+1)]
    #a = [list(map(int, r.split())) for i in range(1,n+1)]
    #a = [list(map(int, input().split())) for i in range(1,n+1)]
    #res = 0

    s = input()
    print('x'*len(s))

if __name__ == '__main__':
    main()


Measured memory_bytes: 38460
n,x=map(int,input().split())
l=list(map(int,input().split()))
ans=0
if l[0]>x:
	ans+=l[0]-x
	l[0]=x
for i in range(1,n):
	s=l[i-1]+l[i]
	if s>x:
		d=l[i]+l[i-1]-x
		ans+=d
		l[i]-=d
print(ans)


Measured memory_bytes: 14252
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <unordered_map>
#include <string.h>
#include<iomanip>
#include <iterator>
#include <locale>

#define all(a) a.begin(),a.end()
#define VV(T) vector<vector< T > >
#define rep(i,N) for(int i = 0; i <N; i++)
#define repsg(i,s,g) for(int i = s; i <g; i++)
#define name(x) #x
using namespace std;


const int INF = 10000000;
const long long INFL = (1LL<<40);
const int MOD = pow(10,9)+7;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

typedef long long ll,LL;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pLL;


// vector入力
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x: vec) is >> x;
    return is;
}
// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){
    for(int i=0; i<vec.size(); i++){
        os << vec[i] << ( i+1 == vec.size() ? "" : " " );
    }
    return os;
}

template< typename T >
struct edge{
    int src, to;T cost;
    edge(int to,T cost) :src(-1),to(to),cost(cost){}
    edge(int src, int to, T cost) :src(src),to(to),cost(cost){}edge
    &operator=(const int &x){
        to =x;
        return *this;
    }
    operator int() const{ return to;}
};



int main() {
    int n,m,x,y;cin>>n>>m>>x>>y;
    vector<int> X(n),Y(m);cin>>X>>Y;
    sort(all(X));sort(all(Y));
    if((X[X.size()-1]<Y[0]) && (Y[0]>x) && (Y[0]<=y)) cout<<"No War" << endl;
    else cout<<"War"<<endl;
    return 0;
}





Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int arr[105][105];
    int b[105];
    bool cond[105][105];
    //vector<int>v;
    int n,i,j;
    for(i=1; i<=3; i++)
    {
        for(j=1; j<=3; j++)
        {
            cin>>arr[i][j];
        }
    }

    int m;
    scanf("%d",&m);
    for(i=1; i<=m; i++)
    {
        cin>>b[i];
    }

    int k,c;
    //c=0;
    //cond=false;
    for(i=1; i<=3; i++)
    {
        for(j=1; j<=3; j++)
        {
            cond[i][j]=false;
            for(k=1; k<=m; k++)
            {
                if(arr[i][j]==b[k])
                {
                    cond[i][j]=true;
                    //c++;
                }
            }
        }
    }

    string res="No";

    for(i=1; i<=3; i++)
    {
        if(cond[i][1]&&cond[i][2]&&cond[i][3])
        {
            res="Yes";
        }
    }

    for(i=1; i<=3; i++)
    {
        if(cond[1][i]&&cond[2][i]&&cond[3][i])
        {
            res="Yes";
        }
    }

    if(cond[1][1]&&cond[2][2]&&cond[3][3])
    {
        res="Yes";
    }

    else if(cond[1][3]&&cond[2][2]&&cond[3][1])
    {
        res="Yes";
    }

    cout<<res;

    printf("\n");
    return 0;

}


Measured memory_bytes: 256
out = [0, 0]

for _ in range(int(input())):
    taro, hanako = input().split()
    if taro > hanako:
        out[0] += 3
    elif taro < hanako:
        out[1] += 3
    else:
        out[0] += 1
        out[1] += 1

print(*out)


Measured memory_bytes: 5600
import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.Maybe (fromJust)
import Data.List as List

solve :: Int -> Int -> Int -> String
solve a b c
    | c >= a && c <= b = "Yes"
    | otherwise = "No"
    

main :: IO()
main = do
    [a, b, c] <- map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine
    putStrLn $ solve a b c


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

#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define MP make_pair
#define test cout<<"test"<<endl;
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ll INF = 1e18;
const ll zero=0;
using P = pair<ll, ll>;
void chmin(ll &a,ll b){if(a>b)a=b;}
void chmax(ll &a,ll b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void pmod(ll &a,ll b,ll c){a=(b+c)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void qmod(ll &a,ll b,ll c){a=(b*c)%MOD;}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
void ans(bool x,ll y,ll z){if(x)cout<<y<<endl;else cout<<z<<endl;}
void ans(bool x,string y,string z){if(x)cout<<y<<endl;else cout<<z<<endl;}   
ll gcd(ll x,ll y){ll r;while((r=x%y)!=0){x=y;y=r;}return y;}

int main(){
  ll i,j,o;
  ll res=0,res1=INF,res2=-INF,buf=0;
  bool judge = true;
  ll n,c,k;cin>>n>>c>>k;
  vector<ll>t(n);
  for(i=0;i<n;i++)cin>>t[i];
  sort(ALL(t));
  ll num=0;
  for(i=0;i<n;i++){
    if(num==0){
      buf=t[i];
      num=1;
    }
    else if(num<c){
      if(buf+k>=t[i])num++;
      else{
        num=1;
        res++;
        buf=t[i];
      }
    }
    else{
      num=1;
      buf=t[i];
      res++;
    }
    //cout<<num spa buf spa res<<endl;
  }
  cout<<res+1<<endl;


  return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

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

        int n = sc.nextInt();
        int a[] = new int[n];

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

        int counter = selectionSort(a, n);
        for (int i=0; i<n-1; ++i) {
            System.out.print(a[i] + " ");
        }
        System.out.println(a[n-1] + "\n" + counter);

        sc.close();
    }

    public static int selectionSort(int a[], int n) {
        int counter = 0;
        int min = 0;
        for (int i=0; i<n; ++i) {
            min = i;
            for (int j=i; j<n; ++j) {
                if (a[j] < a[min]) {
                    min = j;
                }
            }
            if (i != min) {
                int tmp = a[i];
                a[i] = a[min];
                a[min] = tmp;
                counter += 1;
            }
        }
        return counter;
    }
}


Measured memory_bytes: 26240
#include<functional>
#include<algorithm>
#include<iostream>
#include<utility>
#include<string>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,x,n) for(int i=x;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define pf push_front
#define pb push_back
#define int long long
using namespace std;
const int INF=1000000007;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

signed main(){
  string s;
  cin>>s;
  cout<<(s[0]==s[2]?"Yes":"No")<<endl;
  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vpi = vector<pii>;

int n, m, ans = -1;
vvi g;
vi vis;

void dfs(int i) {
    vis[i] = true;
    for (int j : g[i]) {
        if (!vis[j]) dfs(j);
    }
}

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

    cin >> n >> m;
    g.assign(n, vector<int>(0));
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        --x, --y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    vis.assign(n, false);
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            ans++;
            dfs(i);
        }
    }
    cout << ans << "\n";

	return 0;
}


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

using namespace std;

int main()
{
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int res;
    if(c>=b||a>=d)
        res=0;
    else
        res=min(b,d)-max(a,c);
    cout<<res<<endl;
}


Measured memory_bytes: 256
from itertools import accumulate
Q = int(input())

def sieve(n):
    if n == 0:
        return [False]

    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    
    for i in range(2, n + 1):
        for j in range(2 * i, n + 1, i):
            is_prime[j] = False
                
    return is_prime

MAX = 10 ** 5
is_prime = sieve(MAX)
cnt = [0] * (MAX + 1)
for i in range(MAX + 1):
    if is_prime[i] and is_prime[(i + 1) // 2]:
        cnt[i] = 1
cnt = list(accumulate(cnt))

for _ in range(Q):
    l, r = map(int, input().split())
    print(cnt[r] - cnt[l - 1])


Measured memory_bytes: 54148
#include <algorithm>
#include <queue>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <cstdio>
inline int getInt(){ int s; scanf("%d", &s); return s; }

#include <set>

using namespace std;

int main(){
  const int n = getInt();
  vector<int> l(n+n);
  REP(i,n+n) l[i] = getInt();
  sort(l.begin(), l.end());

  int ans = 0;
  REP(i,n) ans += l[i+i];

  printf("%d\n", ans);
  return 0;
}


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

using namespace std;
#define int long long
const int MOD = 1000000007;
map<int, int> mp;
int solve(int N) {
	if (N == 1) return 1;
	if (mp[N] == 0) {
		mp[N] = 1 + 2 * solve(N / 2);
	}
	return mp[N];
}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	cout << solve(N) << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
int main()
{
	long long x, y, z;
	scanf("%lld%lld", &x, &y);
	if (x > y) swap(x, y);
	if (y - x <= 1)
		printf("Brown\n");
	else
		printf("Alice\n");
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std; 
typedef long long ll;
#define pb push_back
#define fi first
#define se second
const ll mod = 1e9+7;
const int N = 2e5+6;
void solve(){
	string s; 
	cin>>s; 
	deque<char> dq;
	for(char c:s)dq.push_back(c);
	int q; 
	cin>>q;
	int ord = 0;
	while(q--){
		int t; 
		cin>>t;
		if(t==1){
			ord = 1-ord;
		}
		else{
			int f;
			cin>>f; 
			char c;
			cin>>c;
			if(f==1){
				if(ord)dq.push_back(c);
				else dq.push_front(c);
			}
			else{
				if(ord==0)dq.push_back(c);
				else dq.push_front(c);
			}
		}
	}
	while(!dq.empty()){
		if(ord==0){
			cout<<dq.front();
			dq.pop_front();
		}
		else{
			cout<<dq.back();
			dq.pop_back();
		}
	}
	cout<<endl;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t=1; 
//	cin>>t; 
	while(t--){
		solve();
	}
	return 0;
}


Measured memory_bytes: 4060
#include<cstdio>
int main()
{
	int n,a;long long ans=0;
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
	{
		scanf("%d",&a);
		while(!(a&1)) a>>=1,++ans; 
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 128
n=int(input())
l=[[j for j,k in enumerate(input())if k=="1"]for i in range(n)]
class UnionFind:
    #def   -> foo=UnionFind(n,1)  <- 1-based index, default is 0
    #method -> foo.hoge(huga)
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)
    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x
        return True
    def size(self, x: int) -> int:
        return -self._parents[self.find(x)]
    def group_count(self) ->int:
        return sum(1 for i in  self._parents if i<0)-self._first_idx
    def connected(self) ->bool:
        return self._parents[self.find(self._first_idx)]==-self._size
uf=UnionFind(2*n)
for i in range(n):
    for ne in l[i]:
        uf.unite(i,ne+n)
        uf.unite(i+n,ne)
notnibu=0
for i in range(n):
    notnibu|=uf.same(i,i+n)
if notnibu:
    print(-1)

else:
    class WarshallFloyd:
        #O(V^3)で任意２頂点の最短距離
        def __init__(self,n,_first_index=0):
            self.v = n
            self._first_idx=_first_index
            self.d = [[float("INF")]*(n) for _ in range(n)]
            for i in range(n):
                self.d[i][i] = 0
    
        def path(self,x,y,c):
            if x == y:
                return False
            f=self._first_idx
            self.d[x-f][y-f] = c
            self.d[y-f][x-f] = c
            return True
    
        def build(self):
            for k in range(self.v):
                for i in range(self.v):
                    for j in range(self.v):
                        self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
            return self.d
    w=WarshallFloyd(n)
    for x in range(n):
        for j in l[x]:
            w.path(x,j,1)
    d=w.build()
    ans=0
    for i in range(n):
        ans=max(ans,max(d[i]))
    print(ans+1)

Measured memory_bytes: 57688
#include<iostream>
#include <algorithm>
#include<string>
#include<math.h>
#include <functional>
using namespace std;

int main(void) {
	int a,b;
	cin >> a >> b;
	cout << (int)( (double)(a+b)/2.0+0.5) << endl;

	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>

using namespace std;

#define REP(i,n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> pint;

ll dp[128][4][4][4];
const ll MOD = 1000000000 + 7;
int main() {
  int N; cin>>N;
  REP(i,4) REP(j,4) REP(k,4) dp[3][i][j][k] = 1;
  dp[3][0][2][1] = 0;
  dp[3][0][1][2] = 0;
  dp[3][2][0][1] = 0;
  for(int n = 4; n <= N; n++) {
    REP(i,4) REP(j,4) REP(k,4) REP(m,4)
    {
      if(i == 0 && k == 2 && m == 1) {
        dp[n][j][k][m] = 0;
      } else if(i == 0 && j == 2 && m == 1) {
        dp[n][j][k][m] = 0;
      } else {
        dp[n][j][k][m] += dp[n-1][i][j][k];
        dp[n][j][k][m] %= MOD;
      }
    }
    dp[n][0][2][1] = 0;
    dp[n][0][1][2] = 0;
    dp[n][2][0][1] = 0;
  }
  ll ans = 0;
  REP(i,4) REP(j,4) REP(k,4) ans += dp[N][i][j][k];
  ans %= MOD;
  cout << ans << endl;
  return 0;
}


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

int main() {
	int n;
	cin >> n;
	long long int l[n+1];
	l[0] = 2;
	l[1] = 1;
	for(int i=0;i<n-1;i++){
		l[i+2] = l[i+1] + l[i];
	}
	cout << l[n] << endl;
	return 0;
}

Measured memory_bytes: 256
//#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"

#define rep(i,n) for(ll (i)=0;(i)<(ll)(n);(i)++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007LL
#define INF (1LL<<60LL)
#define int long long
#define MAX_N (100001)
typedef long long ll;

using namespace std;



signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n; cin >> n;
	vector<int> v(n);
	rep(i, n)cin >> v[i];
	int ans = INF;
	for (int i = 1; i < 101; i++) {
		int k = 0;
		for (auto a : v) {
			k += pow(a - i, 2);
		}
		ans = min(ans, k);
	}
	cout << ans<<endl;
}

Measured memory_bytes: 256
a_price,b_price,ab_price,num_a,num_b = map(int, input().split())
total = 0

if a_price + b_price < 2 * ab_price:
	total = a_price * num_a + b_price * num_b

elif a_price + b_price >= 2 * ab_price:
	if num_a >= num_b:
		if a_price > ab_price * 2:
			total = ab_price * 2 * num_a
		else:
			total = ab_price * 2 * num_b + a_price * (num_a - num_b)
	else:
		if b_price > ab_price * 2:
			total = ab_price * 2 * num_b
		else:
			total = ab_price * 2 * num_a + b_price * (num_b - num_a)

print(total)



Measured memory_bytes: 9216
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

def ketawa(x):
	return sum(map(int, list(str(x))))

N = INT()

ans = INF
for a in range(1, N//2 + 1):
	b = N-a
	ans = min(ans, ketawa(a) + ketawa(b))
print(ans)

Measured memory_bytes: 10492
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0;i<n;i++)
#define repb(i, a, b) for(int i=a;i<b;i++)

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

const int INF = 1<<30;

int main(){
  int MAX_N=int(1e5+2);
  vector<bool> prime(MAX_N, true);
  repb(div, 2, int(sqrt(MAX_N))+1){
    for(int i=div*2;i<MAX_N;i+=div){
    	prime[i]=false;
    }
  }
  prime[0]=prime[1]=false;
  vector<bool> likenum(MAX_N, false);
  rep(i, MAX_N){
    if(i&1==0)continue;
  	likenum[i] = prime[i]&&prime[(i+1)/2];
  }
  vector<int> cnt(MAX_N, 0);
  repb(i, 1, MAX_N){
  	cnt[i]=cnt[i-1]+int(likenum[i]);
  }
  // rep(i, 30)cout<<i<<" "<<cnt[i]<<endl;
  int q;cin>>q;
  rep(i, q){
  	int l, r;cin>>l>>r;
    cout<<cnt[r]-cnt[--l]<<endl;
  }
  return 0;
}



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

using namespace std;

typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = (ll)1e9 + 7;

int main()
{
  int N; scanf("%d", &N);
  int ans = 0, a = 0, least = INF;
  for (int i = 0; i < N; ++i) {
    scanf("%d", &a);
    ans += a;
    if (a % 10 != 0) { least = min(least, a); }
  }

  if (ans % 10 == 0) {
    ans = max(0, ans - least);
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define REP(i, n) for(int i = 0; i < int(n); i++)
#define FOR(i,n,m) for(int i = int(n); i < int(m); i++)
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 6;
const ll LLINF = 1e18 + 1;

template<typename T>
struct Bellman_Ford {
private:
    struct edge { int to; T cost; };
    int V; // 頂点数
    vector<vector<edge>> G;
    vector<T> d;
public:
    const T inf = numeric_limits<T>::max();

    Bellman_Ford(int V) : V(V){
        G.resize(V);
        d.resize(V);
    }

    // 有向辺を張る
    void add_edge(int from, int to, T cost) {
        G[from].push_back({to,cost});
    }

    // 頂点 s からの最短コストを d に入れる
    // sからたどり着く負閉路がある場合 False
    bool build(int s) {
        d.assign(V,inf);
        d[s] = 0;
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                for (edge e : G[j]) {
                    if (d[j] != inf && d[j] + e.cost < d[e.to]) {
                        d[e.to] = d[j] + e.cost;
                        if (i == V - 1) {
                            return false;
                        }
                    }
                }
            }
        }
        /*
        REP(i, V) {
            cout << s << " -> " << i << " = " << d[i] << endl;
        }
        */
        return true;
    }

    // s から v までの最短コスト
    // 行けない場合は inf
    T dist(int v) {
        return d[v];
    }
};

int main() {
    int v, e, s; cin >> v >> e >> s;
    Bellman_Ford<ll> G(v);
    REP(i, e) {
        int a, b;
        ll c;
        scanf("%d %d %lld", &a, &b, &c);
        G.add_edge(a, b, c);
    }
    if (!G.build(s)) {
        puts("NEGATIVE CYCLE");
    }
    else {
        REP(i, v) {
            if (G.dist(i) == G.inf) {
                puts("INF");
            }
            else {
                printf("%lld\n", G.dist(i));
            }
        }
    }
    return 0;
}


Measured memory_bytes: 3292
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> vi;
#define endl '\n'
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define rf(i,a,b) for(int i=a;i>=b;i--) 
#define fast_io ios_base::sync_with_stdio(0);
#define show(x) cout<<x<<endl;
#define pret(x) cout<<x<<endl; return 0;
#define disp(x) cout<<x<<" ";
#define let(x,y) cout<<x<<" "<<y<<endl;
ll MOD=1e9+7;
const int maxn=1e6+5;

bool visited[maxn];
bool v[maxn];
int sp[maxn];		

void Sieve(){
	for (int i = 2; i < maxn; i += 2)	sp[i] = 2;
	for (ll i = 3; i < maxn; i += 2){
		if (!v[i]){
			sp[i] = i;
			for (ll j = i; (j*i) < maxn; j += 2){
				if (!v[j*i])	v[j*i] = true, sp[j*i] = i;
			}
		}
	}
}

int32_t main(){
    fast_io;
    Sieve();
    int n;
    cin >> n;
    int a[n], g = 0;
    for (int i = 0; i < n; ++i)
    {
    	cin >> a[i];
    	g = __gcd(g, a[i]);
    }
    bool flag = 1;
    rf(i, n - 1, 0){
    	int temp = a[i];
    	vi list;
    	while(temp > 1){
    		int curr = sp[temp];
    		list.emplace_back(curr);
    		if(visited[curr]) flag = 0;
    		while(temp % curr == 0) temp /= curr;
    	}
    	for(auto it:list) visited[it] = 1;
    }
	if(flag) {
		show("pairwise coprime");
	}
	else if(g == 1){
		show("setwise coprime");
	}
	else{
		show("not coprime");
	}
    return 0;
}

Measured memory_bytes: 21188
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <array>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <list>
#include <map>
#include <stack>
#include <utility>
#include <bitset>
#include <complex>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <climits>
#include <random>
#include <functional>
#include <sstream>
#include <iomanip>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, m, n) for(int i=(m);i<(n); ++i)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define REVE(x) reverse((x).begin(),(x).end())
#define mp make_pair
#define pb push_back
#define Cout(x) cout << (x) << endl
#define Cout2(x, y) cout << (x) << " " << (y) << endl
#define dump(x) cout << #x << " = " << (x) << endl;
#define forauto(i, a) for(auto i : a)cout << i << " "; puts("");

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef complex<double> CD;

int main() {
	unordered_set<string> s;
	int n; cin >> n;
	rep(i, n) {
		string str, t; cin >> str;
		if (str[0] == 'i') {
			cin >> t;
			s.insert(t);
		}
		else {
			cin >> t;
			auto it = s.find(t);
			puts(it == s.end() ? "no" : "yes");
		}
	}
}


Measured memory_bytes: 31916
n=int(input())
a=list(map(int,input().split()))
ans=True
for i in a:
    if i%2==0:
        if i%3==0:
            pass
        elif i%5==0:
            pass
        else:
            ans=False
if ans==True:
    print('APPROVED')
else:
    print('DENIED')

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define inf (long long)1e18
using namespace std;
int n, m, dist[200001], ans, x, y;
vector <int> adj[200001];
int indeg[200001];
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++){
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        indeg[y]++;
    }
    ans = 0;
    queue <int> q;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0)
            q.push(i);
            
    while (!q.empty()){
        int id = q.front();
        q.pop();
        for (int j = 0; j <(int) adj[id].size(); j++){
            dist[adj[id][j]] = max(dist[adj[id][j]], dist[id] + 1);
            indeg[adj[id][j]]--;
            if (indeg[adj[id][j]] == 0)
                q.push(adj[id][j]);
        }
        ans = max(ans, dist[id]);
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 9088
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstdio>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;

#define rep(i, n) for(int (i) = (0); (i) < (n); (i++))
using P = pair<int, int>;
using ll = long long;

int func(int n){
    if(n == 0) return 0;

    int count = 0;
    while(n % 2 == 0){
        n /= 2;
        count++;
    }

    return count;
}

int main() {
    int n;
    cin >> n;
    int sum = 0;
    rep(i, n){
        int a;
        cin >> a;
        sum += func(a);
    }

    cout << sum << endl;
}

Measured memory_bytes: 764
#include <iostream>
#include <fstream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
#include <bits/stdc++.h>

#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
static const int MOD = 1000000007;
static const ll INF = 1000000000000000000LL;
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; }


vector <vector <int> >  G;
vector <vector <int> > color;


//根付き木として扱う

int main(){
  ll N;
  cin >> N;

  color.resize(N);
  G.resize(N);

  vector <int> a(N-1);
  vector <int> b(N-1);

  REP(i,N-1)
  {
    cin >> a[i] >> b[i];
    --a[i];--b[i];
    G[a[i]].push_back(b[i]);
    G[b[i]].push_back(a[i]);
  }

  int iMax = 0;

  REP(i,N)
  {
    int tmp = G[i].size();
    iMax = max(iMax, tmp);
  }
  //iMax+1で塗り分けられる

  //cout << iMax << endl;

  map<std::pair<int, int>, int> map_r;
  vector<int> cs(N,0); // color of edge between its parent
  vector<int> used(N,0);

  queue<ll> que;
  //ゴールを追加
  que.push(0);
  used[0] = 1;

  while(!que.empty())
  {
    auto v = que.front();
    que.pop();
    int cur = 1;
    for(ll i = 0; i < G[v].size(); ++i)
    {
      ll u = G[v][i];
      if(used[u] == 1)continue;
      if(cur == cs[v])cur++;
      cs[u] = map_r[(make_pair(v, u))] = map_r[(make_pair(u, v))] = cur++;
      used[u] = 1;
      que.push(u);
      
    }
  }

  cout << iMax << endl;

  REP(i,N - 1)
  {
    auto tmp = map_r.find(make_pair(a[i],b[i]));

    cout << tmp->second  << endl;
  }
  return 0;    
}



Measured memory_bytes: 22400
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>
#include <stdio.h>
#include <string.h>
using ll = long long;

//LLONG_MAX
#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define LOWER_BOUND(v,a) (lower_bound((v).begin(), (v).end(), (a)))
#define UPPER_BOUND(v,a) (upper_bound((v).begin(), (v).end(), (a)))
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define CONTAINS_MAP(m, a) (m).find((a)) != m.end()
using namespace std;

queue<int> s[1001];
int day[1001] = {};

int N;

signed main()
{
	cin >> N;
	REP(i, N) REP(j, N - 1)
	{
		int a;
		cin >> a;
		a--;
		s[i].push(a);
	}

	int loop_begin = 0;
	int cur = 0;
	int cnt = 0;
	while(true)
	{
		if (s[cur].size() == 0)
		{
			cur = (cur + 1) % N;
			if (cur == loop_begin) { cout << -1 << endl; return 0; }
			continue;
		}
		int s1 = s[cur].front();

		if (s[s1].size() == 0)
		{
			cur = (cur + 1) % N;
			if (cur == loop_begin) { cout << -1 << endl; return 0; }
			continue;
		}
		int s2 = s[s1].front();

		if (s2 == cur)
		{
			int d = max(day[s1], day[s2]);
			day[cur] = d + 1;
			day[s1] = d + 1;
			loop_begin = cur;
			s[cur].pop();
			s[s1].pop();
			cnt++;
		}
		else
		{
			cur = (cur + 1) % N;
			if (cur == loop_begin) { cout << -1 << endl; return 0; }
		}

		if (cnt == (N * (N - 1)) / 2)
		{
			break;
		}
	}

	int m = 0;
	for (int i = 0; i < N; i++)
	{
		m = max(m, day[i]);
	}
	cout << m << endl;
}




Measured memory_bytes: 8960
import numpy as np
    
n = int(input())
S = np.asarray([])
St = np.zeros(4) # None,B,A,BA
count = 0

for i in range(n):
    S=np.append(S,input())
    tmp = 0
    count += S[i].count("AB")
    if S[i][0] == "B":
        tmp += 1
    if S[i][-1] == "A":
        tmp += 2
    St[tmp]+=1

if (St[1] == 0)&(St[3]>0):
    St[1]+=1
    St[3]-=1

if (St[2] == 0)&(St[3]>0):
    St[2]+=1
    St[3]-=1

print(int(count+min(St[1],St[2])+St[3]))

Measured memory_bytes: 14516
//c++ テンプレ
#include<bits/stdc++.h>
using namespace std;

typedef long long llint;
typedef long double ld;

#define inf 1e18
#define mod 1000000007
#define sort(v) sort(v.begin(),v.end())
#define reverse(v) reverse(v.begin(),v.end())

priority_queue<llint,vector<llint>,greater<llint> > que;
priority_queue<llint> Que;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

int ans;
int h,w,k;
vector<string>c;

void solve(){
    
    cin >> h >> w >> k;
    c.resize(h);
    for(int i=0;i<h;i++)cin >> c[i];
    int ans=0;
    for(int bh=0;bh<(1<<h);bh++){
        for(int bw=0;bw<(1<<w);bw++){
            int cnt=0;
            for(int i=0;i<h;i++){
                for(int j=0;j<w;j++){
                    if(bh>>i&1)continue;
                    if(bw>>j&1)continue;
                    if(c[i][j]=='#')cnt++;
                }
            }
            if(cnt==k)ans++;
        }
    }
    cout << ans << endl;
}

int main(){
    solve();
    return 0;
}




Measured memory_bytes: 3616
n = int(input())
A = list(map(int, input().split()))
tot = sum([abs(A[i] - A[i - 1]) if i != 0 else abs(A[0]) for i in range(n)]) + abs(A[-1])
A = [0, ] + A + [0, ]
for i in range(1, n + 1):
    if min(A[i - 1], A[i + 1]) <= A[i] <= max(A[i - 1], A[i + 1]):
        print(tot)
    else:
        print(tot - (abs(A[i] - A[i - 1]) + abs(A[i + 1] - A[i]) - abs(A[i + 1] - A[i - 1])))


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


#define M 1000000007
#define pb push_back
#define mp make_pair
#define s second
#define f first
#define mod 998244353
#define sz(v) (int)(v).size()

#define pii pair<int, int>
#define vi vector<int>
#define ll long long
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)

ll add(ll a,ll b)
{
	a%=M;
	b%=M;
	ll p = (a+b)%M;
	return (p+M)%M;
}

ll mul(ll a,ll b)
{
	a%=M;
	b%=M;
	ll p = (a*b)%M;
	return (p+M)%M;
}


int main()
{
	fastio;
	ll n;
	cin>>n;
	if((n%10==7)||((n/10)%10==7)||((n/100)%10==7))
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
    return 0;
}





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

int main(){
	int n;
	cin >> n;
	int a[100002]{};
	while(n--){
		int l, r;
		cin >> l >> r;
		a[--l]++;
		a[r]--;
	}
	for(int i = 1; i < 100002; i++) a[i] += a[i - 1];
	int ans = 0;
	for(int i = 0; i < 100002; i++) ans += a[i];
	cout << ans << endl;
}

Measured memory_bytes: 640
#include <iostream> // cout, endl, cin
#include <cmath> //sqrt pow
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
 
#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define mod 1000000007
using ll = long long;
using namespace std;
bool check(int n, vi &d){
  while(n){
    if(!d[n % 10]) return false;
    n /= 10;
  }
  return true;
}
int main(){
  int n,k;
  cin >> n >> k;
  vi d(10, 1);
  rep(i, k){
    int D;
    cin >> D;
    d[D] = 0;
  }
  for(int i = n; ; i++){
    if(check(i, d)){
      cout << i << endl;
      return 0;
    }
  }
}

Measured memory_bytes: 256
#pragma region template 2.4
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using pq_asc = priority_queue<T, vector<T>, greater<T>>;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP1(i, n) for (ll i = 1; i <= (n); ++i)
#define FOR(i, a) for (auto &i : a)
#define CH(f, x, y) x = f(x, y)
#define IN(T, x) \
    T x;         \
    cin >> x;
#define AIN(T, a, n) \
    vector<T> a(n);  \
    FOR(i, a)        \
    cin >> i;
#define A2IN(T1, a, T2, b, n) \
    vector<T1> a(n);          \
    vector<T2> b(n);          \
    REP(i, n)                 \
    cin >> a[i] >> b[i];
#define OUT(x) cout << (x) << endl;
#define FOUT(x) cout << fixed << setprecision(15) << (x) << endl;
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) \
    SORT(a);     \
    reverse(ALL(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define DUMPA(a)          \
    cout << #a << " = {"; \
    JOUT(ALL(a), ", ", cout) << "}" << endl;

template <typename T>
ostream &JOUT(T s, T e, string sep = " ", ostream &os = cout)
{
    if (s != e)
    {
        os << *s;
        ++s;
    }
    while (s != e)
    {
        os << sep << *s;
        ++s;
    }
    return os;
}

ostream &YES(bool cond, string yes = "Yes", string no = "No", ostream &os = cout)
{
    if (cond)
    {
        os << yes << endl;
    }
    else
    {
        os << no << endl;
    }
    return os;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p)
{
    os << '(' << p.first << ", " << p.second << ')';
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << '[';
    JOUT(ALL(v), ", ", os) << ']';
    return os;
}

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#pragma endregion template

int main()
{
    IN(ll, N);
    AIN(ll, A, N);
    ll ans = 0;
    REP1(i, N)
    {
        ans += (i % 2 == 1) and (A[i - 1] % 2 == 1);
    }
    OUT(ans);
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,x,n) for(int i=x;i<n;i++)
#define mod 1000000007 //10^9+7
#define INF 1000000000000 //10^12
#define F first
#define S second
#define P pair<int,int>
#define all(vec) vec.begin(),vec.end()
signed main(){
    string s;
    cin>>s;
    bool ans=true;
    int l=s.size();
    rep(i,l){
        if(s[i]!=s[l-i-1])ans=false;
    }
    string t=s.substr(0,(l-1)/2);
    rep(i,t.size()){
        if(t[i]!=t[(l-1)/2-i-1])ans=false;
    }
    string u=s.substr((l+3)/2-1);
    rep(i,u.size()){
        if(u[i]!=u[(int)u.size()-i-1])ans=false;
    }
    if(ans)puts("Yes");
    else puts("No");
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String str = sc.nextLine();
    StringBuilder ans = new StringBuilder("");
    for(int i = 0; i < str.length(); i++) {
      char ch = str.charAt(i);
      switch(ch) {
        case '0':
        case '1':
          ans.append(ch);
          break;
        case 'B':
          if(ans.length() != 0) {
            ans.deleteCharAt(ans.length() - 1);
          }
          break;
      }
    }
    System.out.println(ans);
  }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;

int main(){
    int n,m,x; cin >> n >> m >> x;
    vi c(n);
    vvi a(n,vi(m));
    bitset<12> bb;
    for(int ix=0;ix<n;ix++){
        cin >> c.at(ix);
        for(int ix2=0;ix2<m;ix2++){
            cin >> a.at(ix).at(ix2);
        }
    }
    int64_t purchase=1000000007;
    for(int ix=0;ix<(1<<n);ix++){
        bb = ix; bool can = true; int64_t tmp=0;
        vi test(m,0);
        for(int ix2=0;ix2<n;ix2++){
            if(bb.test(ix2)){
                tmp+=c.at(ix2);
                for(int ix3=0;ix3<m;ix3++){
                    test.at(ix3) += a.at(ix2).at(ix3);
                }
            }
        }
        for(int ix4=0;ix4<m;ix4++) if(test.at(ix4)<x) can = false;
        if(can) purchase = min(purchase,tmp);
    }
    cout << (purchase != 1000000007 ? purchase : (int64_t)-1) << endl;
}

Measured memory_bytes: 3636
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define in insert
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int INF = 1e9 + 5;
int main(){
    int n;
    cin >> n;
    vi a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    ll dp1[n-1], dp2[n-1];
    dp1[0] = a[0];
    dp2[0] = -a[0];
    //cout << dp1[0] << " " << dp2[0] << endl;
    for(int i = 1; i < n-1; i++){
        dp1[i] = max(dp1[i-1] + a[i], dp2[i-1] - a[i]);
        dp2[i] = max(dp1[i-1] - a[i], dp2[i-1] + a[i]);
        //cout << dp1[i] << " " << dp2[i] << endl;
    }
    cout << max(dp1[n-2] + a[n-1], dp2[n-2] - a[n-1]);
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
#define F first
#define S second
#define $ ios::sync_with_stdio(0);
#define endl '\n'
using namespace std;
using ll = long long int;
using ii = pair<ll, ll>;
using vi = vector<int>;
using vii = vector<ii>;
using graph = vector<vi>;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 212345;
const ll mod = 1000000007;
int fq[30];
int main() {
    string s;
    cin >> s;
    for (auto i : s) {
        fq[i-'a']++;
    }
    bool ans = 1;
    for (int i = 0; i<26; ++i) {
        if (fq[i]&1) ans = 0;
    }
    puts(ans ? "Yes":"No");

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define fo(i,n)         for(int i=0;i<n;i++)
#define Fo(i,k,n)       for(int i=k;i<n;i++) 
#define endl            "\n"
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define vec(x)          vector<x>
#define matrix(x)       vector<vector<x>>
#define mem(a,b)        memset(a, b, sizeof a)
#define vii             vector<pair<int,int>>
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define MOD             998244353
#define deb(x)          cerr <<#x<<" = "<<x<<"\n"
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define all(v)          v.begin(),v.end()
#define rep(i,a,b)      for (int i = a; i<b; ++i)
#define len(s)          s.length()
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
 
 
int power(int a,int b,int m=mod)
{int ans=1;while(b>0){if(b&1)ans=(ans*a)%m;a=(a*a)%m;b>>=1;}
return ans;}

void angshuGod()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

const int N = 1e5+10;
const double pi = acos(-1);
vi adj[N];
bool visited[N];
vi ans(N);
int cnt = 0;

void dfs(int node, int par){
    visited[node] = true;
    ans[node] = par;
    for(int x : adj[node]){
        if(!visited[x])
            dfs(x,node);
    }
}
int parent[N];
void bfs(int node, int par){
    visited[node] = true;
    queue<int>q;
    q.push(node);
    while(!q.empty()){
        int f = q.front();
        q.pop();
        for(int x : adj[f]){
            if(!visited[x]){
                parent[x] = f;
                visited[x] = true;
                q.push(x);
            }
        }
    }
}

void solve(){    

    
    int n,m;
    cin>>n>>m;
    mem(visited,false);
    while(m--){
        int a,b;
        cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    for(int i = 1;i<=n;i++){
        if(!visited[i]){
            cnt++;
            bfs(i,-1);
        }
    }
    if(cnt>1){
        cout<<"No\n";
    }
    else{
        cout<<"Yes\n";
        for(int i = 2;i<=n;i++)
            cout<<parent[i]<<"\n";
    }
}

 
int32_t main()
{
    angshuGod();

    int t;

    t = 1;
    //cin>>t;

    while(t--){
        solve();
    }
    
    return 0;
}

Measured memory_bytes: 13704
#include<bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
using pqueg = priority_queue<int, vector<int>, greater<int>>;
using pquel = priority_queue<int, vector<int>, less<int>>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
int lcm(int a, int b){
  return a / __gcd(a, b) * b;
}
int r_int(int a, int b){
  return rand() % b + a;
}
const lint mod=1e9+7;



int main()
{
  lint n, k;
  cin >> n >> k;
  vector<lint> h(n);
  REP(i,n) cin >> h[i];

  sort(ALL(h));
  lint cnt = 0;
  REP(i,h.size()-k) cnt += h[i];

  cout << cnt << "\n";
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define REP(i, m, n) for(int (i) = (m); (i) < (n); ++i)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
using namespace std;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
typedef long long ll;
typedef pair<ll, ll> P;
const int INF = 1e9+7;
const ll LINF = 1LL<<60;

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<int> p(n);
    rep(i, n) {
        cin >> p[i];
    }
    int i = 0;
    int ans = 0;
    while(i < n) {
        if (p[i] == i + 1) {
            ans += 1;
            i += 2;
        } else {
            i++;
        }
    }

    cout << ans << endl;

    return 0;
}

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

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

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

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

// Problem Specific Parameter:
const ll mod=1000000007LL;

const int limit=1000010;

ll dp[limit];
ll csum[limit];

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

	dp[0]=1LL;
	rep(i,1,n+1){
		csum[i]=(csum[i]+csum[i-1])%mod;
		dp[i]=(csum[i]+dp[i-1])%mod;
		csum[i+2]=(csum[i+2]+dp[i-1])%mod;
	}

	ll ans=(n+1LL*(n-1)*(n-1))%mod;

	rep(i,1,n){
		ll cur=n-1;
		if(i<n-1) cur+=1LL*(n-1)*(n-1);
		cur%=mod;
		const ll add=1LL*cur*dp[i]%mod;
		ans=(ans+add)%mod;
	}
		
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 15872
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
	string s;
	int i,ans=0;
	cin>>s;
	for(i=0;i<s.size();i++)
		ans+=s[i]-'0';
	if(ans%9)
		cout<<"No";
	else
		cout<<"Yes";
	return 0;
}

Measured memory_bytes: 3752