akhauriyash/Code-Regression huggingface dataset:
// ※※※ 解答不能 ※※※
// 正答者のソースを学習する.
// satashun氏.
// https://atcoder.jp/contests/abc136/submissions/6697878
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

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

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for(int i = m; i < (n); i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cout << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p){
    os<<"("<<p.first<<","<<p.second<<")";
    return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v){
    os<<"{";
    rep(i, v.size()){
        if (i) os<<",";
        os<<v[i];
    }
    os<<"}";
    return os;
}

const ll MOD = 998244353;
const int MN = 200010;

// 1-indexed, [1, n]
template<class T>
class BIT{
    T bit[MN];
    int n;
public:
    BIT(){
        n = MN;
        memset(bit, 0, sizeof(bit));
    }
    T sum(int i){
        ++i;
        T s = 0;
        while(i > 0){
            s += bit[i];
            i -= i & -i;
        }
        return s;
    }
    void add(int i, T x){
        ++i;
        while(i < n){
            bit[i] += x;
            i += i & -i;
        }
    }
};

int num[MN][4];
ll p2[MN];

void init(){
    p2[0] = 1;
    for(int i = 1; i < MN; ++i) p2[i] = p2[i - 1] * 2 % MOD;
}

int main(){
    
    init();
    int N;
    scanf("%d", &N);
    vector<pii> vec(N);
    vi xs, ys;
    
    rep(i, N){
        int x, y;
        scanf("%d %d", &x, &y);
        vec[i] = mp(x, y);
        xs.pb(x); ys.pb(y);
    }
    
    sort(ALL(xs)); sort(ALL(ys));
    rep(i, N){
        int x = vec[i].fi, y = vec[i].se;
        x = lower_bound(ALL(xs), x) - xs.begin();
        y = lower_bound(ALL(ys), y) - ys.begin();
        vec[i] = mp(x, y);
    }
    
    sort(ALL(vec));
    rep(t, 2){
        BIT<int> T;
        rep(i, N) {
            int a = T.sum(vec[i].se - 1), b = i - T.sum(vec[i].se);
            if(t == 0){
                num[i][0] = a;
                num[i][1] = b;
            }else{
                num[N - 1 - i][2] = a;
                num[N - 1 - i][3] = b;
            }
            T.add(vec[i].se, 1);
        }
        reverse(ALL(vec));
    }
    
    ll ans = 0;
    rep(i, N) {
        ll a = (p2[num[i][0]] + p2[num[i][3]] - 1) % MOD;
        ll b = (p2[num[i][1]] + p2[num[i][2]] - 1) % MOD;
        ll v = (p2[N] - a * b) % MOD;
        if (v < 0) v += MOD;
        ans = (ans + v) % MOD;
    }
    
    printf("%llu", ans);
    return 0;
}

Measured memory_bytes: 9068
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdio.h>
#include <map>
#include <set>
#include <utility>
#include <queue>
#include <bitset>
#include <math.h>
#include <numeric>
#include <stack>

using namespace std;
 
#define rep(i,m,n) for(int i=m;i<(int)(n);i++)
#define endl '\n'
typedef long long ll;

int gcd(int x,int y){
    return y ? gcd(y,x%y) : x;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n; cin >> n;
    int d[n];
    rep(i,0,n) cin >> d[i];
    int sum = 0;
    rep(i,0,n){
        rep(j,i+1,n)sum += d[i]*d[j];
    }
    cout << sum << endl;
}


Measured memory_bytes: 256
ans_list = []

while True:
    n = int(input())
    if n == 0:
        break
    A = list(map(int,input().split()))
    ave = sum(A) / len(A)
    cnt = 0
    for a in A:
        if a <= ave:
            cnt += 1
    ans_list.append(cnt)

for ans in ans_list:
    print(ans)


Measured memory_bytes: 6612
N, M = map(int, input().split())  #数字
H = list(map(int, input().split()))#リスト
A = [list(map(int, input().split())) for i in range(M)]  #数字、複数行複数列

good = [True]*N
for i, j in A:
    i -= 1
    j -= 1
    if H[i] < H[j]:
        good[i] = False
    if H[i] > H[j]:
        good[j] = False
    if H[i] == H[j]:
        good[i] = False
        good[j] = False

print(good.count(True))

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

int main() {
    ll n, m;
    cin >> n >> m;
    ll ans =0;
    if(n==2 || m==2){
        cout << 0 << endl;
        return 0;
    }if(n==1 || m==1){
        if(n==1 && m==1){
            cout << 1 << endl;
            return 0;
        }
        cout << max(n,m)-2 << endl;
        return 0;
    }else{
        ans = n*m-(2*m+(n-2)*2);
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.List;

public class Main {
    public static void main(String args[]) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int d=sc.nextInt();
        int arr[][]=new int[n][d];
        for (int i=0;i<n;i++){
            for (int j=0;j<d;j++){
                arr[i][j]=sc.nextInt();
            }
        }
        int cnt=0;
        for (int i=0;i<n;i++){
            for (int j=i+1;j<n;j++){
                int sum=0;
                for (int k=0;k<d;k++){
                    sum+=((arr[i][k]-arr[j][k])*(arr[i][k]-arr[j][k]));
                }
                int tmp=sum;
                int sqrt=(int)Math.sqrt(tmp);
                if (sqrt*sqrt==sum){
                    cnt++;
                }
            }
        }
        System.out.println(cnt);



    }

}



Measured memory_bytes: 21844
from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
D = defaultdict(int)

for i in A:
  D[i] += 1

L1 = [0, 0]
L2 = [0]

for i, x in D.items():
  if x >= 4:
    L2.append(i)
  if x >= 2:
    L1.append(i)

L1.sort(reverse=True)
L2.sort(reverse=True)

print(max(L1[0]*L1[1], L2[0]**2))

Measured memory_bytes: 22192
k = int(input())

count = [pow(k // max(i, 1), 3) for i in range(k + 1)]

for i in range(k, 0, -1):
  for j in range(2 * i, k + 1, i):
    count[i] -= count[j]

sum_ = 0
for i in range(k + 1):
  sum_ += i * count[i]

print(sum_)

Measured memory_bytes: 9196
N = int(input())
A = []
for i in range(N):
	A.append(int(input()))

A = sorted(A)

x = A[0]
s = 0
c = 0
for i in range(N):
	if A[i] == x:
		c += 1
	else:
		x = A[i]
		if c % 2 == 1:
			s += 1
		c = 1

if c % 2 == 1:
	s += 1

print(s)

Measured memory_bytes: 8284
M, D = map(int, input().split())
ans = 0

for m in range(1, M+1):
  for d in range(11, D+1):
    d = str(d)
    d10 = int(d[0])
    d1 = int(d[1])
    
    if d1 >= 2 and d10 >= 2 and m == d1 * d10:
      ans += 1
    
print(ans)

Measured memory_bytes: 39152
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  unsigned long long a[N], sum = 0;
  cin >> a[0];
  for(int i = 1; i < N; i++) {
    cin >> a[i];
    if(a[i-1] > a[i]) {
      sum += a[i-1] - a[i];
      a[i] = a[i-1];
    }
  }
  cout << sum << endl;
}

Measured memory_bytes: 5064
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */


template<class Type>
Type solve(Type res = Type()){
    int A,B,C; cin >> A >> B >> C;
    res = max({10*A+B+C,A+10*B+C,A+B+10*C});
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    //test();
    //solve<ll>();
    cout << fixed << setprecision(15) << solve<ll>() << endl;
    return 0;
}



Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <complex>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <stdio.h>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<double> VEC;
typedef vector<VEC> MAT;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
//container util

//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define MT(a,b,c) MP(a, MP(b, c))
#define T1 first
#define T2 second.first
#define T3 second.second.first
#define T4 second.second.second

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EPS 1.0e-9

int main(){
	double x1, x2, x3, y1, y2, y3, xp, yp;
	while(cin>>x1>>y1>>x2>>y2>>x3>>y3>>xp>>yp){
		double a = x2-x1;
		double b = x3-x1;
		double c = xp-x1;
		double d = y2-y1;
		double e = y3-y1;
		double f = yp-y1;
		double s = (c*e-b*f)/(a*e-b*d);
		double t = (a*f-c*d)/(a*e-b*d);
		if(s+t<1 && s>0 && t>0)cout << "YES" << endl;
		else cout <<"NO" <<endl;
	}
	return 0;
}

Measured memory_bytes: 1220
#include <iostream>
#include <string>
#include <algorithm>
#include <ctime>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cassert>
#include <bitset>
#include <list>
#include <cstdio>
#include <stdio.h>
#include <string.h>
#define rep(i,n) for(int i=0; i<(n); i++)
typedef long long ll;
using namespace std;

int main()
{
    string s;
    cin >> s;
    int n = s.size();
    int ans1 = 0,ans2 = 0;
    rep(i,n)
    {
        if(i%2==0 && s[i]=='0') ans1++;
        if(i%2==1 && s[i]=='1') ans1++;
    }
    rep(i,n)
    {
        if(i%2==1 && s[i]=='0') ans2++;
        if(i%2==0 && s[i]=='1') ans2++;
    }
    cout << min(ans1, ans2) << endl;
    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <numeric>
#include <queue>
#include <deque>

using namespace std;
using ll = long long int;

struct work{
    ll duration, dead;
};

int main(){
    ll N;
    cin >> N;
    vector<work> W(N);
    for(ll i = 0; i < N; ++i){
        cin >> W[i].duration >> W[i].dead;
    }

    sort(W.begin(), W.end(), [](work const &a, work const &b){
        return a.dead < b.dead;
    });
    ll time = 0;
    for(ll i = 0; i < N; ++i){
        time += W[i].duration;
        if(time > W[i].dead){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;

    return 0;
}


Measured memory_bytes: 3328
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;



int main(){
    string T,S;
    cin>>S;
    cin>>T;

    int ans=1e5+10;
    int i=0;
    do{
        int c=0;
        for(int k=0;k<T.size();k++){
            if (T[k]!=S[i+k]) c++;
        }
        ans=min(c,ans);
        i++;
    }while(i<S.size()-T.size());

    printf("%d\n",ans);

    return 0;
}



Measured memory_bytes: 3720
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main(void)
{
	ll a,b,c,d;
	cin>>a>>b>>c>>d;
	ll ans1,ans2,ans3,ans4;
	ans1=a*c;
	ans2=a*d;
	ans3=b*c;
	ans4=b*d;
	cout<<max(ans1,max(ans2,max(ans3,ans4)));
	return 0;
}

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

int main(){
  int N, m;
  cin >> N;
  vector<int>B(N, 0);
  rep(i, N - 1){
   cin >> m;
    --m;
   B[m]++; 
  }
  rep(i, N){
   cout << B[i] << endl; 
  }
  return 0;
}

Measured memory_bytes: 3980
/**
 * C - Exception Handling
 * https://atcoder.jp/contests/abc134/tasks/abc134_c
 **/
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

const int MAX_N = 200000;

int N;
vector<int> a;
vector<int> ans;
int max_a[2];

void solve() {
    for (int i=0; i<N; i++) {
        if(max_a[0] == a[i]) {
            ans.push_back(max_a[1]);
        } else {
            ans.push_back(max_a[0]);
        }
    }
    for (int i=0; i<ans.size(); i++) {
        cout << ans[i] << endl;
    }
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        int tmp;
        cin >> tmp;
        a.push_back(tmp);
    }
    vector<int> copy_a = a;
    sort(copy_a.begin(), copy_a.end(), greater<int>());
    max_a[0] = copy_a[0];
    max_a[1] = copy_a[1];
    solve();
}


Measured memory_bytes: 4084
#pragma GCC optimize("Ofast")
    #include<bits/stdc++.h>
    //#include <ext/pb_ds/assoc_container.hpp> 
    #define vi vector<long long int>
    #define ll long long 
    #define mp make_pair
    #define p push
    #define pb push_back
    #define np next_permutation
    #define fin(i,a,b) for(int i=a;i<b;i++)
    #define max3(a,b,c) max(max(a,b),c)
    #define min3(a,b,c) min(min(a,b),c)
    //typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;
    const ll INF =1e18;
    const ll mod =1e9+7;
    using namespace std;
    const int N = 50000;
    int checkprime(int n){
        for(int i=2;i<min(N,n);i++){
            if(n%i==0)return 0;
        }
        return 1;
    }
    //using namespace __gnu_pbds;

    int main(){

        #ifdef _DEBUG
        freopen("input.txt", "r", stdin);
    //	freopen("output.txt", "w", stdout);
    #endif
        ios::sync_with_stdio(0); 
        cin.tie(0);
        cout.tie(0);
        //code from here>>
        ll t;
        cin>>t;
        ll ans=0;
        for(int i=1;i<=t/2;i++){
           if(t%i==0){
               ans+=t/i-1;
           }else{
              ans+= t/i;
           }
        }
        if(t%2==0){
            ans+=t/2-1;
        }else{
            ans+=t/2;
        }
        cout<<ans<<endl;
    
            
        
        
        
        return 0;
    }


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

int main(){
    int a,b,c,k;
    bool ok=true;
    long long big=0;
    cin >> a >> b >> c >> k;
    big=max(a,(max(b,c)));
    if(big==a){
        for(int i=0;i<k;i++){
            big *= 2;
        }
        cout << big + b + c << endl;
        ok=false;
    }
    if(big==b&&ok){
        for(int i=0;i<k;i++){
            big *= 2;
        }
        cout << a + big + c << endl;
        ok=false;
    }
    if(big==c&&ok){
        for(int i=0;i<k;i++){
            big *= 2;
        }
        cout << a + b + big << endl;
        ok=false;
    }
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,fa[110000],z;
int find(int x)
{return (fa[x]==x)?(x):(fa[x]=find(fa[x]));}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		fa[i]=i;z=n;
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		x=find(x);y=find(y);
		if(x==y)continue;
		z--;fa[x]=y;
	}
	printf("%d",z-1);
}

Measured memory_bytes: 2116
def list_avr(list):
  total = sum(list)
  avr = round(total / len(list))
  return avr

health = 0
n = int(input())
x = list(map(int,input().split()))
avr = list_avr(x)

for i in range(n):
  health += (x[i]-avr)**2

print(health)
      

Measured memory_bytes: 38256
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    n = i_input()
    l = [i_list() for i in range(n)]
    l = sorted(l, key= lambda x: x[1])

    trial = 0
    for i,k in l:
        trial += i
        if trial > k:
            print("No")
            exit()
    print("Yes")


if __name__=="__main__":
    main()


Measured memory_bytes: 48820
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
#define era(t) t.erase(unique(be(t)),t.end())
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;
typedef long long ll;
using namespace std;
const ll mod=1000000007,mod9=1000000009;
template <class T>inline T lcm(T a,T b){return (a*b/__gcd(a,b));}

void U(int n){
    for(int i=0;i<n;i++){
        cout << 'U';
    }
}
void R(int n){
    for(int i=0;i<n;i++){
        cout << 'R';
    }
}
void L(int n){
    for(int i=0;i<n;i++){
        cout << 'L';
    }
}
void D(int n){
    for(int i=0;i<n;i++){
        cout << 'D';
    }
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    d-=b;
    c-=a;
    U(d);
    R(c+1);
    D(d+1);
    L(c+1);
    U(1);
    L(1);
    U(d+1);
    R(c+1);
    D(d+1);
    L(c);
    cout << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long

using namespace std;

const int MAXN = (int) 1e5;

bool ciur[MAXN + 1];
int sp[MAXN + 1];

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int n, i, j, q;
    ios::sync_with_stdio(false);
    for(i = 2; i * i <= MAXN; i++) {
        if(ciur[i] == 0)
            for(j = i * i; j <= MAXN; j += i)
               ciur[j] = 1;
    }
    ciur[1] = ciur[0] = 1;
    for(i = 2; i <= MAXN; i++) {
        sp[i] = sp[i - 1];
        if(ciur[i] == 0 && ciur[(i + 1) / 2] == 0)
            sp[i]++;
    }
    cin >> q;
    while(q > 0) {
        q--;
        int l, r;
        cin >> l >> r;
        cout << sp[r] - sp[l - 1] << "\n";
    }
    //cin.close();
    //cout.close();
    return 0;
}


Measured memory_bytes: 1152
import itertools
import sys
import math
import numpy as np
from collections import deque
from itertools import combinations
from functools import lru_cache
sys.setrecursionlimit(10**9)


def main():
    H,A = map(int,input().split())

    m,r = divmod(H,A)

    print(m if r == 0 else m + 1)

if __name__ == "__main__":
  main()


Measured memory_bytes: 21252
#include<bits/stdc++.h>
using namespace std;
string a,b;
int main(){
    cin>>a>>b;
    int len=max(a.length(),b.length());
    for(int i=0;i<len;i++){
        if(a[i]!='\0')putchar(a[i]);
        if(b[i]!='\0')putchar(b[i]);
    }
    cout<<endl;
    return 0;
}

Measured memory_bytes: 256
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_D
#include <iostream>
using namespace std;

int main(){

  int n,m,l;
  cin >> n >> m >> l;
  long long A[n][m];
  long long B[m][l];
  long long c[n][l];

  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      cin >> A[i][j];
    }
  }

  for(int i = 0; i < m; i++){
    for(int j = 0; j < l; j++){
      cin >> B[i][j];
    }
  }

  for(int i =0; i < n; i++){
    for(int j = 0; j < l; j++){
      c[i][j] = 0;
      for(int k = 0; k<m; k++){
        c[i][j] += A[i][k]*B[k][j];
      }
    }
  }


  for(int i = 0; i < n; i++){
      for(int j = 0; j < l-1; j++){
        cout << c[i][j] << " ";
      }
    cout << c[i][l-1] << endl;
  }
}

Measured memory_bytes: 1396
#include <iostream>
#include <string>
#include <vector>
#include <algorithm> 
#include <utility> 
#include <tuple> 
#include <cstdint> 
#include <cstdio> 
#include <map> 
#include <queue> 
#include <set> 
#include <stack> 
#include <deque> 
#include <unordered_map> 
#include <unordered_set> 
#include <bitset> 
#include <cctype> 
#include <cmath>
#include <iomanip>
#include <ctype.h>
#include <numeric>
#include <iterator>

using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi >;
using vl = vector<ll>;
using vvl = vector<vl >;
using pairi = pair<int, int>;
using pairl = pair<ll, ll>;

#define TR ","
#define TS " "
#define rep(i,N) for(int i=0;i<(int)N;++i)
#define rpt(i,a,b) for(ll i=a;i<(ll)b;++i)
#define all(v) v.begin(), v.end()
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)

ll gcd(ll a, ll b) {
    if (a < b) swap(a, b);
    if (b == 0) return a;
    return gcd(b, a % b);
}

ll lcm(ll x, ll y) {
    return x / gcd(x, y) * y;
}

ll waz = 76543217;

void printVector(const vector<int>& vec) {
    for (int value : vec) {
        cout << value << " ";
    }
    cout << endl;
}

int A[1000000], n;

int binarySearch(int key) {
    int left = 0;
    int right = n;
    int mid;
    while (left < right) {
        mid = (left + right) / 2;
        if (key == A[mid]) return 1;
        if (key > A[mid]) left = mid + 1;
        else if (key < A[mid]) right = mid;
    }
    return 0;
}

int main()
{
    IO;

    int i, q, k, sum = 0;
    
    cin >> n;
    rep(i, n) cin >> A[i];

    cin >> q;
    rep(i, q) {
        cin >> k;
        if (binarySearch(k)) ++sum;
    }

    cout << sum << endl;

    return 0;

}


Measured memory_bytes: 3472
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(long long i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,n-1,0)
#define RREPS(i,n) RFOR(i,n,1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true; }return false; }
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true; }return false; }
const int INF = 1e18;

signed main(){
    int n; cin >> n;
    vector<pair<int,int>> p(n);
    REP(i,n){
        int a; cin >> a;
        p[i] = {a,i};
    }
    sort(rall(p));
    multiset<int> d;
    d.insert(n);
    d.insert(n);
    d.insert(-1);
    d.insert(-1);
    int ans = 0;
    REP(i,n){
        int now = p[i].second;
        int right, nright, left, nleft;
        auto itr = d.lower_bound(now);
        itr++;
        nright = *itr;
        itr--;
        right = *itr;
        itr--;
        left = *itr;
        itr--;
        nleft = *itr;
      	ans += ((right-now) * (left-nleft) + (now-left) * (nright-right)) * p[i].first;
        d.insert(now);
    }
    cout << ans << endl;
}

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

int gcd(int x, int y);

const int INF = 1001001001;

//mint�p�̕ϐ� (10��9��)
const int mod = 1000000007;

struct mint {
    ll x; // typedef long long ll;
    mint(ll x = 0) :x((x% mod + mod) % mod) {}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; }
    mint operator+(const mint a) const { return mint(*this) += a; }
    mint operator-(const mint a) const { return mint(*this) -= a; }
    mint operator*(const mint a) const { return mint(*this) *= a; }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod - 2); }
    mint& operator/=(const mint a) { return *this *= a.inv(); }
    mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream & is, const mint & a) { return is >> a.x; }
ostream& operator<<(ostream & os, const mint & a) { return os << a.x; }


int main() {
    vector <ll> num(3);
    ll ans = 1;
    cin >> num[0] >> num[1] >> num[2];

    if (num[0] % 2 == 0 || num[1] % 2 == 0 || num[2] % 2 == 0) {
        cout << 0 << endl;
        return 0;
    }
    sort(num.begin(), num.end());
    ans = num[0] * num[1];
    cout << ans << endl;
    return 0;
}
/*���C�u�����ő����*/
//���[�O���b�h�̌ݏ��@
int gcd(int x, int y) {
    int num[3];
    num[0] = (x > y) ? x : y;
    num[1] = (x <= y) ? x : y;
    num[2] = num[0] % num[1];

    while (num[2]) {
        num[0] = num[1];
        num[1] = num[2];
        num[2] = num[0] % num[1];
    }

    return num[1];
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_int.hpp>
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E17;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
////////////////////////////
//区間和
struct RSQ{
    ll n;
    vector<ll>data;
    RSQ(ll vs){
        n=1;
        while(n<vs)n*=2;
        data.resize(2*n-1,0);
    }
    void update(ll k,ll a){
        k+=n-1;
        data[k]=mod(a);
        while(k>0){
            k=(k-1)/2;
            data[k]=mod(data[2*k+1]+data[2*k+2]);
        }
    }
    /*
    void add(ll k,ll a){
        k+=n-1;
        data[k]+=a;
        while(k>0){
            k=(k-1)/2;
            data[k]=data[2*k+1]+data[2*k+2];
        }
    }
     */
    ll query(ll a,ll b,ll k,ll l,ll r){
        if(r<=a||b<=l)return 0;
        if(a<=l&&r<=b){
            return data[k];
        }else{
            ll vl=query(a,b,2*k+1,l,(l+r)/2);
            ll vr=query(a,b,2*k+2,(l+r)/2,r);
            return mod(vl+vr);
        }
    }
    ll query(ll a,ll b){return query(a,b,0,0,n);}//[a,b)の和
};
//////////////////////////////////////////////////////
ll n,ans=0;
vector<ll>v;
bool check(){
    rep(i,0,n-2){
        ll k=v[i+1];
        for(ll j=i+2;j<=n-1&&j<=i+v[i];j++){
            if(v[j]!=k)return false;
        }
    }
    rep(i,0,n-1)cout<<v[i]<<" ";cout<<endl;
    ans++;
    return 0;
}
void dfs(ll c){
    c++;
    if(c==n){
        check();
    }else{
        rep(i,1,n){
            v.pb(i);
            dfs(c);
            v.pop_back();
        }
    }
}
int main(){
    cin>>n;
    if(n==1){
        cout<<1;return 0;
    }
    RSQ r(n+1);
    r.update(1,n);
    r.update(2,mod(n*n));
    rep(m,3,n){
        ll sum=mod((n-m+2)*n);
        Add(sum,(m-3)*(n-1));
        Add(sum,r.query(m-1,m));
        Add(sum,r.query(1,m-2));
        r.update(m,sum);
    }
    cout<<mod(r.query(n,n+1))<<endl;
    /*
    rep(i,1,n){
        cout<<i<<":"<<mod(r.query(i,i+1))<<endl;
    }
    
    dfs(-1);
    cout<<ans<<endl;
    */
    return 0;
}


Measured memory_bytes: 16640
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

a =int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()




if a >= 3200:
    print(S
          )
else:
    print('red')


Measured memory_bytes: 23100
N = int(input())
S = [int(i) for i in str(N)]
L = len(S)
sum = 0
i = 0

while i < L:
    sum = sum + int(S[i])
    i = i + 1
    
if (sum % 9) == 0:
    print("Yes")
else:
    print("No")



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

using namespace std;

int MAX = 123456 * 2 + 1;
int N;
int cnt[123456 * 2 + 1];

void countPrime() {
	memset(cnt, 0, sizeof(cnt));
	vector<bool> isPrime(MAX, true);
	
	for (int i = 2; i <= MAX; i++) {
		if (isPrime[i]) {
			cnt[i] = cnt[i - 1] + 1;
			for (int j = 2 * i; j <= MAX; j += i) isPrime[j] = false;
		} else {
			cnt[i] = cnt[i - 1];
		}
	}
}


int main() {
	countPrime();
	
	while (1) {
		cin >> N; if (N == 0) break;
		cout << cnt[2 * N] - cnt[N] << endl;
	}
	
	return 0;
}

Measured memory_bytes: 2196
import fractions
from functools import reduce
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)#数列に対しての最小公倍数
n = int(input())
t=[]
for i in range(n):
    t.append(int(input()))
print(lcm(*t))

Measured memory_bytes: 5688
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  int x, a, b, c;
  cin >> x;
  a = x % 2;
  b = ( x - a ) % 4 / 2;
  c = ( x - a - b ) % 8 / 4;
  cout << a + b + c << endl;
}

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

int main(){
  int teamn = 0;
  cin >> teamn;
  vector<int> point(teamn,0);
  vector<int> run(teamn,0);
  vector<int> plist;
  vector<int> rank(teamn,1);
  int fteam1,fteam2;
  int point1,point2;
  for(int n = 0;n<(teamn*(teamn-1))/2;n++){
    cin >> fteam1 >> fteam2;
    cin >> point1 >> point2;
    fteam1 -= 1;
    fteam2 -= 1;
    if(point1 > point2){
      point[fteam1] += 3;
    }else
    if(point1 == point2){
      point[fteam1] += 1;
      point[fteam2] += 1;
    }else
    if(point1 < point2){
      point[fteam2] += 3;
    }
  }
  for(int g = 0;g<point.size();g++){
    run[g] = point[g];
  }
  sort(run.begin(),run.end(),greater<int>());
  //for(int n = 0;n<run.size();n++){
  //  if(run[n] != run[n+1]){
  //    plist.push_back(run[n]);
  //  }
  //}
  for(int n = 0;n<run.size();n++){
    for(int g = 0;g<point.size();g++){
      if(n == 0 && run[n] == point[g]){
        rank[g] = n;
      }
      if(run[n] == point[g] && n != 0){
        if(run[n] != run[n-1]){
          rank[g] = n;
        }
      }
    }
  }
  for(int n = 0;n<rank.size();n++){
    cout << rank[n]+1 << endl;
  }
  return 0;
}

Measured memory_bytes: 1216
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vii;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n;
  cin>>n;
  if( n % 2 == 0){ cout<<n<<"\n";}
  else{ cout<<n*2<<"\n"; }
  return 0;
}


Measured memory_bytes: 256
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <ctime>
#include <map>
#include <stack>
#include <sstream>
#include <set>
#include <cmath>
#include <functional>
#include <memory.h>

// pi = atan(1)*4;

#define INTMAX 2100000000

using namespace std;

int main(void)
{
	int a, b, c;

	cin >> a >> b >> c;

	if (2*b == a + c)
	{
		cout << "YES" << '\n';
	}
	else
	{
		cout << "NO" << '\n';
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pci pair<char, int>
#define pic pair<int, char>
#define plvl pair<long long, vector<long long> >
#define pcvc pair<char, vector<char> >


using namespace std;

const int mod = 1e9 + 7;

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

template <typename T>
void show1(vector<T> dp) {
	for(auto d : dp) {
		cout << d << " ";
	}
	cout << "\n";
}

template <typename T>
void show2(vector<vector<T> > dp) {
	for(auto d : dp) {
		for(auto dd : d) {
			cout << dd << " ";
		}
		cout << "\n";
	}
}

void executeCode() {
		ll a, b;
		cin >> a >> b;
		cout << a * b << "\n";
}

int main() {
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int tt = 1;
	// cin >> tt;
	while(tt--) {
		executeCode();	
	}
	return 0;
}

Measured memory_bytes: 3588
def add_list(list, s)
  index = 0

  while index < list.length
    if list[index].nil?
      list[index] = s
      return list
    elsif list[index] < s
      index += 1
    elsif list[index] == s
      return list
    else
      if index + 1 < list.length
        list[(index+1)..-1] = list[index..-2]
      end

      list[index] = s
      return list
    end
  end

  return list
end

s = gets.chomp
k = gets.chomp.to_i

hash = {}

s.chars.each_with_index do |c, i|
  if hash[c].nil?
    hash[c] = [i]
  else
    hash[c] << i
  end
end

char_hash = hash.sort
list = Array.new(k)

char_hash.each do |v|
  v[1].each do |i|
    k.times do |j|
      break if i+j >= s.length
      list = add_list(list, s[i..(i+j)])
    end
  end

  break if list[-1] != nil
end

puts list[-1]


Measured memory_bytes: 2172
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#define rep(i, N) for (int i=0; i<(int)N; i++)

using namespace std;

int main() {
  string str_;
  cin >> str_;
  if (str_ == "AAA" || str_ == "BBB") {
    cout << "No";
  } else {
    cout << "Yes";
  }
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define repr(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repr(i,0,n)
#define reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define PI 3.1415926535
typedef long long ll;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<Pll> vPll;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
typedef vector<vector<double>> vvd;
typedef vector<vector<Pi>> vvPi;
typedef priority_queue<int, vector<int>, greater<int>> pqli;
typedef priority_queue<ll, vector<ll>, greater<ll>> pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi>> pqlP;
string YN(bool y) { return (y?"YES":"NO"); }
string yn(bool y) { return (y?"Yes":"No"); }
string ON(bool y) { return (y?"OK":"NG"); }
int main(void)
{
	int n;

	cin>>n;

	vi a(n), count(9, 0);

	rep(i, n) cin>>a[i];

	rep(i, n){
		int temp=a[i]/400;
		if(temp<8){
			count[temp]++;
		}else{
			count[8]++;
		}
	}
	if(count[8]!=0){
		int ans=0;
		rep(i, 8){
			if(count[i]!=0) ans++;
		}
		int min=(ans!=0)?ans:1;
		cout<<min<<" "<<ans+count[8]<<endl;

	}else{
		int ans=0;
		rep(i, 8){
			if(count[i]!=0) ans++;
		}
		cout<<ans<<" "<<ans<<endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
const bool debug=true;
#define DEBUG if(debug==true)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int n,a[3];
vector<string> strs;
void dfs(string s){
    if(s.size()==n-1){
        rep(i,4){
            strs.push_back(s+to_string(i));
        }
    }else{
        rep(i,4){
            dfs(s+to_string(i));
        }
    }
}

int main(void) {
    cin >> n;
    rep(i,3)cin >> a[i];
    int l[n];
    rep(i,n)cin >> l[i];
    dfs("");
    // DEBUG{
    //     cout << strs.size() << endl;
    // }
    int cost,res=INT_MAX;
    rep(i,strs.size()){
        int cnt[3]={};
        int tmp=stoi(strs[i]);
        // DEBUG{
        //     cout << i << endl;
        //     cout << tmp << endl;
        // }
        int cur=0;
        cost=0;
        rep(j,n){
            cur=tmp%10;
            // DEBUG{cout << cur << endl;}
            tmp/=10;
            if(cur==3)continue;
            else if(cnt[cur]!=0){
                cost+=10;
            }
            cnt[cur]+=l[j];
        }
        rep(j,3){
            if(cnt[j]==0){
                cost=INT_MAX;
                break;
            }
            cost += abs(cnt[j]-a[j]);
        }
        if(cost<res)res=cost;
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 3832
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
mod = int(1e9 + 7)
notbroken = [True for _ in range(n+1)]

for i in a:
  notbroken[i] = False

dp = [0 for _ in range(n+1)]
dp[0] = 1
if notbroken[1]: dp[1] = 1

for i in range(2, n+1):
    if notbroken[i]:
        dp[i] += dp[i-1] + dp[i-2]
        dp[i] %= mod

print(dp[n])

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

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

void solve() {
    ll N;
    cin >> N;
    Vl A(N + 1);
    for (ll i = 1; i <= N; i++) {
        cin >> A[i];
    }
    ll ans = 0;
    for (ll i = 1; i <= N; i++) {
        if (i & 1 && A[i] & 1) {
            ++ans;
        }
    }
    cout << ans << "\n";
}

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

int main() {
#ifdef FASTIO
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(false);
#endif
#ifdef FILEINPUT
    ifstream ifs("./in_out/input.txt");
    cin.rdbuf(ifs.rdbuf());
#endif
#ifdef FILEOUTPUT
    ofstream ofs("./in_out/output.txt");
    cout.rdbuf(ofs.rdbuf());
#endif
    solve();
    cout << flush;
    return 0;
}

Measured memory_bytes: 3648
import collections
N,Q=map(int,input().split())
arr=[[] for i in range(N)]

for i in range(N-1):
    a,b=map(int,input().split())
    arr[a-1].append(b-1)
    arr[b-1].append(a-1)

lis=[0]*N
for i in range(Q):
    a,b=map(int,input().split())
    lis[a-1]+=b


#print(lis)
vist=[0]*N
d=collections.deque()
d.append(0)
while d:
    a=d.pop()
    vist[a]=1
    
    for j in arr[a]:
        
        if vist[j]==1:
            continue
        lis[j]+=lis[a]
        d.append(j)
 #   print(a,d,lis,vist)



print(*lis)

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

int main(void)
{
    int n, k, counter = 0, longest = 0;
    string str;
    cin >> n >> k >> str;
    bool flag = 0;
    bool flag_beginning = 0;
    bool flag_last = 0;
    vector<int> one, zero;

    if (str.at(0) == '1')
    {
        flag_beginning = 1;
        flag = 1;
    }
    if (str.at(n - 1) == '1')
    {
        flag_last = 1;
    }

    for (int i = 1; i < n; i++)
    {
        if (str.at(i) == str.at(i - 1))
        {
            counter++;
            if (i == n - 1)
            {
                if (flag)
                {
                    one.push_back(counter + 1);
                    flag = 0;
                }
                else
                {
                    zero.push_back(counter + 1);
                    flag = 1;
                }
            }
        }
        else
        {
            if (i == n - 1)
            {
                if (flag)
                {
                    one.push_back(counter + 1);
                    zero.push_back(1);
                    flag = 0;
                }
                else
                {
                    zero.push_back(counter + 1);
                    one.push_back(1);
                    flag = 1;
                }
            }
            else
            {
                if (flag)
                {
                    one.push_back(counter + 1);
                    flag = 0;
                }
                else
                {
                    zero.push_back(counter + 1);
                    flag = 1;
                }
            }
            counter = 0;
        }
    }

    if (zero.size() == 0)
    {
        cout << n << endl;
    }
    else if (one.size() == 0)
    {
        if (k == 0)
        {
            cout << 0 << endl;
        }
        else
        {
            cout << n << endl;
        }
    }
    else if (zero.size() <= k - 1) //forgetting this is the reason of RE
    {
        cout << n << endl;
    }
    else
    {
        //was RE
        if (flag_beginning == 0)
        {
            for (int j = 0; j < k; j++)
            {
                longest += zero.at(j);
                longest += one.at(j);
            }
        }

        //was RE
        for (int i = 0; i < one.size() - k; i++)
        {
            int sum = 0;
            for (int j = 0; j < k; j++)
            {
                sum += zero.at(i + j + (1 - flag_beginning));
                sum += one.at(i + j);
            }
            sum += one.at(i + k);
            if (sum > longest)
            {
                longest = sum;
            }
        }

        //OK
        if (flag_last == 0)
        {
            reverse(zero.begin(), zero.end());
            reverse(one.begin(), one.end());
            int sum = 0;
            for (int j = 0; j < k; j++)
            {
                sum += zero.at(j);
                sum += one.at(j);
            }
            if (sum > longest)
            {
                longest = sum;
            }
        }

        cout << longest << endl;
    }

    return 0;
}


Measured memory_bytes: 1020
N = int(input())
A = []
A.append(0)
B = [int(i) for i in input().split()]
A.extend(B)
A.append(0)

s = sum([abs(A[i]-A[i+1]) for i in range(N+1)])

for i in range(1,N+1):
    print(s-abs(A[i]-A[i-1])-abs(A[i+1]-A[i])+abs(A[i+1]-A[i-1]))

Measured memory_bytes: 15840
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		int a=0;
		int b=0;
		int M=0;
		int S=0;
		
		Scanner scan = new Scanner(System.in);
		a=Integer.parseInt(scan.next());
		b=Integer.parseInt(scan.next());
		M=a*b;
		S=2*a+2*b;
		System.out.println(M+" "+S);
    }
}

Measured memory_bytes: 26120
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void solve() {
	int n;
	cin >> n;
	if (n >= 30)
		cout << "Yes";
	else
		cout << "No";
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#if defined(_DEBUG)
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int q = 1;
	//cin >> q;
	for (; q > 0; q--) {
		solve();
		cout << endl;
	}
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
const char nl = '\n';
using namespace std;
using ll = long long;
using ld = long double;
const int MOD = 1e9+7;
const int N = 2e5+10;

ll pw(ll x, ll e) {
  ll ans = 1;
  for (; e; e /= 2, x = (x*x) % MOD) {
    if (e%2) ans = (ans*x) % MOD;
  }
  return ans;
}

ll fac[N], ifac[N], inv[N];
void pre() {
  fac[0] = ifac[0] = 1;
  inv[1] = 1;
  for (int i = 2; i < N; i++) {
    inv[i] = (MOD - (ll) (MOD/i) * inv[MOD%i] % MOD) % MOD; }
  for (int i = 1; i < N; i++) {
    fac[i] = fac[i-1] * i % MOD;
    ifac[i] = ifac[i-1] * inv[i] % MOD;
  }
}

ll choose(ll n, ll k) {
  if (k < 0 || k > n) return 0;
  return fac[n] * ifac[k] % MOD * ifac[n-k] % MOD;
}

ll now[N], nob[N], ow[N];

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  pre();
  int b, w; cin >> b >> w;
  ow[0] = 1;
  for (int i = 1; i < b+w; i++) {
    now[i] = (now[i-1] + choose(i-1, w-1) * pw(inv[2], i)) % MOD;
    nob[i] = (nob[i-1] + choose(i-1, b-1) * pw(inv[2], i)) % MOD;
    ow[i] = (1 - now[i] - nob[i] + 2*MOD) % MOD;
    //cerr << now[i] << " ";
  }
  now[b+w] = nob[b+w] = 1;
  for (int i = 1; i <= b+w; i++) {
    // P(i is black) = P(no white) + 1/2 P(<W, <B eaten)
    cout << (now[i-1] + inv[2] * ow[i-1]) % MOD << nl;
  }
  //cerr << nl;
  return 0;
}


Measured memory_bytes: 11648
#include<iostream>
#include<bits/stdc++.h>
#include<vector>
#define vi vector<int>
#define lli long long int
#define fo(i,n) for(int i=1;i<=n;i++)
#define foo(i,n) for(int i=0;i<n;i++)
#define ff first
#define ss second
#define pb push_back
#define vii vector<lli>

#define ok ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
#define vp vector<pair<lli,lli>>
#include <map>           
lli mod=1000000007;         


/*int main(){
  lli n,x,t;
  cin>>n>>x>>t;
  if(n%x == 0){
  	cout<<(n/x * t);
  }
  else cout<<((n/x + 1)*t);
//  cout<<(n%x==0)?(n/x * t):(n/x + 1)*t;
}*/

int main(){
	string s;
	cin>>s;
	lli sum=0;
	for(char c:s){
		sum+=(c-'0');
	}
	if(sum%9) cout<<"No";
	else cout<<"Yes";
}

/*int main(){
	lli n,mxx,s=0;
	cin>>n;
	vi v(n),mx(n);
	foo(i,n) cin>>v[i];
	mxx=v[0];
//	cout<<mxx;

    foo(i,n){
    	if(v[i]>mxx)
    	mxx=v[i];
    	s+=abs(mxx-v[i]);
	}

for(int i=1;i<=n-1;i++)
	{
		if(v[i]>mxx)
		mx[i]=v[i],mxx=v[i];
		else mx[i]=mxx;
	}
	foo(i,n){
		s+=abs(v[i]-mx[i]);
	}
	
//	foo(i,n) cout<<mx[i]<<" ";
	cout<<s;
}*/







Measured memory_bytes: 3684
import java.io.*;
public class Main {
  public static void main (String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    String line = br.readLine();
    int x = 0;
    int max = 0;
    for (int i = 0; i < n; i++) {
      String s = line.substring(i, i+1);
      if (s.equals("I")) {
        x++;
      } else if (s.equals("D")) {
        x--;
      }
      if (max < x) {
        max = x;
      }
    }
    System.out.println(max);
  }
}


Measured memory_bytes: 8268
#include <stdio.h>

int	main()
{
  char	S[3];
  int	cnt = 0;
  int	flag = 0;
  
  scanf("%s", S);
  for (int i = 0; S[i] ;i++)
  {
    if (S[i] == 'R' && flag == 0)
    {
      cnt = 1;
      flag = 1;
    }
    else if (S[i] == 'R' && flag == 1)
    {
      cnt++;
    }
    else
    {
      flag = 0;
    }
  }
  printf("%d\n",cnt);
}

Measured memory_bytes: 2152