akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define e1 first
#define e2 second
#define pb push_back
#define mp make_pair
#define boost ios_base::sync_with_stdio(false)
#define eb emplace_back
#define OUT(x) {cout << x; exit(0); }
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define scanf(...) scanf(__VA_ARGS__)?:0
typedef long long int ll;
typedef unsigned long long ull;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair <PLL, int> PLLI;
typedef pair <PLL, PLL> PP;
typedef pair <PII, int> PPI;
typedef pair <ll, int> PLI;
typedef unsigned int ui;
const int mod = 1000000;
const int inf = 1e9+9;
const ll MOD = 1e9+696969;
const long long INF = 1e18+3;
int PI[5010];

int main()
{
	int xd;
	cin >> xd;
	string s, w;
	cin >> s >> w;
	int sz = (int)s.size() + (int)w.size();
	s = "#" + w + "$" + s;
	int n = s.size(), b = 0;
	PI[b] = 0;
	for (int i=2; i<n; ++i)
	{
		while (b > 0 && s[i] != s[b + 1]) b = PI[b];
		if (s[i] == s[b + 1]) ++b;
		PI[i] = b;
	}
	
	cout << sz - PI[n - 1];
	
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
const int INF = 1 << 29;

template <class T, class Compare = less<T>>
class SlideRangeQuery {
 private:
  const vector<T>& vs;

  Compare comp;
  int x = 0;
  deque<int> deq;

 public:
  SlideRangeQuery(const vector<T>& vs_) : vs(vs_) {}

  // [a, b)
  int query(int a, int b) {
    while (!deq.empty() && deq.front() < a) {
      deq.pop_front();
    }
    for (x = max(a, x); x < b; x++) {
      while (!deq.empty() && not comp(vs[deq.back()], vs[x])) {
        deq.pop_back();
      }
      deq.push_back(x);
    }
    return deq.empty() ? -1 : deq.front();
  }
};

template <class T>
using SlideMinimum = SlideRangeQuery<T, less<T>>;

template <class T>
using SlideMaximum = SlideRangeQuery<T, greater<T>>;

int main() {
  int N, W;
  while (cin >> N >> W) {
    vector<int> v(N), w(N), m(N);
    for (int i = 0; i < N; i++) cin >> v[i] >> w[i] >> m[i];
    vector<int> dp(W + 1);
    for (int i = 0; i < N; i++) {
      for (int r = 0; r < w[i]; r++) {
        vector<int> b;
        for (int j = 0; w[i] * j + r <= W; j++)
          b.push_back(dp[w[i] * j + r] - v[i] * j);
        SlideMaximum<int> sm(b);
        for (int j = 0; w[i] * j + r <= W; j++)
          dp[w[i] * j + r] = b[sm.query(max(0, j - m[i]), j + 1)] + j * v[i];
      }
    }
    int res = *max_element(dp.begin(), dp.end());
    cout << res << endl;
  }
  return 0;
}



Measured memory_bytes: 3260
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

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

    int r = 1, t = 1;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;

        t *= 3;
        r *= a % 2 == 0 ? 2 : 1;
    }

    cout << t - r << endl;

    return 0;
}

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


#define fi first
#define se second
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define el '\n'

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

const int N = 2e5 + 10;

ll n;
ll ans;

ll hitung(ll a, ll b){
    if (a > b) swap(a, b);
    return a * (n - b + 1LL); 
}

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

    cin >> n;
    for (ll i=1;i<=n;i++){
        ans += i * ((ll)n - i + 1LL);
    }
    for (ll i=1;i<n;i++){
        ll a, b;
        cin >> a >> b;
        ans -= hitung(a, b);
    }
    cout << ans << el;

    return 0;
}

Measured memory_bytes: 3664
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        while(true){
            int sum = 0;
            int n = sc.nextInt();
            int x = sc.nextInt();
            
            if(n == 0){
                break;
            }
            
            for(int i = 1; i <= n; i++){
                for(int j = i + 1; j <= n; j++){
                    for(int k = j + 1; k <= n; k++){
                        if(i + j + k == x){
                            sum++;
                        }
                    }
                }
            }
            
            System.out.println(sum);
        }
    }
}



Measured memory_bytes: 26580
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>

int main(){
    int n, t, a;
    std::cin >> n;
    std::cin >> t >> a;
    std::vector<long long> h(n);

    std::vector<double> r;
    for(int i = 0; i < n; i++){
        std::cin >> h[i];
        double k = t - h[i] * 0.006;
        r.push_back(std::abs(a - k));
    }
    auto itr1 = std::min_element(r.begin(), r.end());
    auto ind = std::distance(r.begin(), itr1);
    std::cout << ind + 1 << std::endl;
    return 0;
}


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


int main(void)
{
    int a, b;
    cin >> a >> b;
    
    // Nth Equation
    int N;
    N = b - a;
   
    int F=0;
    for(int i=1; i<N+1; i++){
        F = F+i;
    }
    
    cout << F-b << endl;
    
    
    return 0;
}

Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
a.reverse()
ans=[]
re_ans=[]
if n==1:
    print(a[0])
else:
    ans=a[::2]
    re_ans=a[1::2]
    re_ans.reverse()
    ans.extend(re_ans)
    map_ans=map(str,ans)
    v=" ".join(map_ans)
    print(v)

Measured memory_bytes: 30404
def S(i,x,y):
	d=2*max(x,y)-sum(a)
	return d if d>=0 else min(S(i+1,x+a[i],y),S(i+1,x,y+a[i]))
while 1:
	if input()==0:break
	a=sorted(map(int,raw_input().split()))[::-1]
	print S(1,a[0],0)

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

int main(void){
	int n;
	while(cin>>n,n){
		int t[n+1][n+1];
		memset(t,0,sizeof(t));
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				cin>>t[i][j];
				t[n][j] += t[i][j];
				t[i][n] += t[i][j];
			}
		}

		for(int i=0;i<n+1;i++){
			for(int j=0;j<n+1;j++){
				printf("%5d",t[i][j]);
				if(i < n && j == n) t[n][n] += t[i][j];
			}
			cout<<endl;
		}
	}

	return 0;
}

Measured memory_bytes: 0
import java.io.*;
import java.util.StringTokenizer;

class Main {
    public static void main(String args[]) {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String buf;

	try {
	    while (!(buf = br.readLine()).equals("-1 -1 -1")) {
		StringTokenizer st = new StringTokenizer(buf);
		int h = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int s = Integer.parseInt(st.nextToken());
		int residual = 120*60-(h*3600+m*60+s);
		System.out.printf("%02d:%02d:%02d%n",residual/3600,(residual%3600)/60,residual%60);
		residual *= 3;
		System.out.printf("%02d:%02d:%02d%n",residual/3600,(residual%3600)/60,residual%60);
	    }
	} catch (Exception e) {
	    e.printStackTrace();
	}
    }
}

Measured memory_bytes: 17000
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, A;
  cin >> N >> A;
  
  if (N - 500 * (N/500) <= A){
   cout << "Yes" << endl; 
  }
  else {
   cout << "No" << endl; 
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<vector>
#define ll long long
#define MAX 1000003
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define endl "\n"
#define all(a) (a).begin(),(a).end()
#define input(a) for(int i=0;i<n;i++) cin>>a[i];
using namespace std;

int main(){
	IOS;
	int n; cin>>n;
	vector<int> a(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}	
	int ctr=0,max_len=INT_MIN;
	for(int i=0;i<n-1;i++){
		if(a[i]>=a[i+1])
			ctr++;
		else{
			max_len=max(max_len,ctr);
			ctr=0;
		}
	}

	cout<<max(max_len,ctr);
return 0;
}

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

typedef long long int ll;

// ====================================================================

int main() {
  // 入力
  int n;
  cin >> n;
  vector<ll> v(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i];
  }

  // 2通り試す
  ll ans1 = 0, ans2 = 0, sowa = 0;
  // 最初がプラスのパターン
  for (int i = 0; i < n; i++) {
    sowa += v[i];
    if (i % 2 == 0) {
      if (sowa <= 0) {
        ans1 += 1 - sowa;
        sowa = 1;
      }
    } else {
      if (sowa >= 0) {
        ans1 += 1 + sowa;
        sowa = -1;
      }
    }
  }

  // 最初がマイナスのパターン
  sowa = 0;
  for (int i = 0; i < n; i++) {
    sowa += v[i];
    if (i % 2 == 1) {
      if (sowa <= 0) {
        ans2 += 1 - sowa;
        sowa = 1;
      }
    } else {
      if (sowa >= 0) {
        ans2 += 1 + sowa;
        sowa = -1;
      }
    }
  }

  cout << min(ans1, ans2) << endl;
}


Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int max=-1,p;
	for(int i=1;i<=n;i++)
	{
		int temp=i,sum=0;
		while(temp%2==0)
		{
			sum++;
			temp/=2;
		}
		if(sum>max)
		{
			max=sum;
			p=i;
		}
	}
	cout<<p;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <string>
#include <set>
#include <iomanip>
#include <map>
#define rep(i,n) for (int i=0;i<(n);++i)
using namespace std;
using ll = long long;

int main(){
    string s, s2;
    int ans = 0;
    cin >> s >> s2;
    for(int i = 0; i < 3; ++i){
        if(s[i] == s2[i])
            ++ans;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
int main(){
    int n;
    cin >> n;
    int a[100][2];
    for (int i=0; i<n; i++){
        cin >> a[i][0] >> a[i][1];
    }
    // Be careful when the loop ends
    for (int i=0; i<n-2; i++){
        if(a[i][0]==a[i][1] && a[i+1][0]==a[i+1][1] && a[i+2][0]==a[i+2][1]){
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";
}

Measured memory_bytes: 3644
#include "bits/stdc++.h"
using namespace std;


/* macro */
#define rep(i,a,b) for(int i=a;i<b;i++)
#define revrep(i,a,b) for(int i = a; i > b; i--)
#define int long long
#define exist(s,e) ((s).find(e)!=(s).end())
#define all(v) (v).begin(), (v).end()
#define each(s,itr) for(auto (itr) = s.begin(); (itr) != s.end(); (itr)++)
#define sum(v) accumulate(all(v), (0LL))


/* alias */
template<class T> using vec = vector<T>;
typedef vector<int> vi;
typedef pair<int, int> pi;


/* constant */
const int inf = 100100100100100100;
const int mod = 1e9;
int dx[8]={1,0,-1,0,-1,1,-1,1};
int dy[8]={0,1,0,-1,-1,-1,1,1};


/* io_method */
int input(){int tmp;cin >> tmp;return tmp;}
string raw_input(){string tmp;cin >> tmp;return tmp;}
string readline(){string s;getline(cin, s);return s;}
template<class T> void printx(T n){cout << n;}
template<class T, class U> void printx(pair<T, U> p){cout << "(" << p.first << "," << p.second << ")";}
template<class T> void printx(vector<T> v){cout << "{";rep(i,0,v.size()){printx(v[i]);if(i != v.size()-1)printx(",");}cout << "}";}
template<class T> void print(T n){printx(n);cout << endl;}
template<class T> void print(set<T> s){cout << "{";each(s, e){if(e != s.begin()) printx(",");printx(*e);}cout << "}" << endl;}
template<class T, class U> void print(map<T, U> mp){cout << "{";each(mp, e){cout << "(" << e -> first << "," << e -> second << ")";}cout << "}" << endl;}


/* general_method */
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
vector<int> cs(vector<int> arr){vector<int> tmp;if(arr.size() == 0) return tmp;tmp.push_back(arr[0]);rep(i,1,arr.size()){tmp.push_back(tmp.back() + arr[i]);}return tmp;}



/* main */



signed main(){

    cin.tie(0);
    ios::sync_with_stdio(false);



 
    int n = input();

    vi arr; rep(i,0,n) arr.push_back(input());
    sort(all(arr));

    if(n == 2){
        print(abs(arr[0] - arr[1]));
        return 0;
    }

    deque<int> q;

    q.push_back(arr[0]);
    q.push_back(arr.back());

    int l = 1, r = n - 2;

    while(!(l > r)){

        int ltob = abs(arr[l] - q.back());
        int ltof = abs(arr[l] - q.front());
        int rtob = abs(arr[r] - q.back());
        int rtof = abs(arr[r] - q.front());

        if(ltob >= ltof && ltob >= rtob && ltob >= rtof){
            q.push_back(arr[l]);

            l++;
        }else if(ltof >= ltob && ltof >= rtob && ltof >= rtof){
            q.push_front(arr[l]);

            l++;
        }else if(rtob >= ltob && rtob >= ltof && rtob >= rtof){
            q.push_back(arr[r]);
            r--;
        }else if(rtof >= ltob && rtof >= ltof && rtof >= rtob){
            q.push_front(arr[r]);

            r--;
        }

    }
    vi tmp;
    each(q, itr){
        tmp.push_back(*itr);
    }

    int ans = 0;
    rep(i,1,n){
        ans += abs(tmp[i - 1] - tmp[i]);
    }

    print(ans);
    


    

    
   
    













}






    










    




    










Measured memory_bytes: 3444
#include <iostream>
#include <vector>
#include <map>
using namespace std;
using pint = pair<int,int>;

int N;
vector<vector<int> > G;

map<pint,int> ma;
int rec2(int v, int p, int c) {
    if (ma.count(pint(v, c))) return ma[pint(v, c)];
    int res = 1;
    for (auto ch : G[v]) {
        if (ch == p) continue;
        if (ch > c) continue;
        res += rec2(ch, v, c);
    }
    return ma[pint(v, c)] = res;
}

vector<int> res;
void rec(int v, int p, int mp) {
    if (mp > v) {
        res[v] = res[p] - rec2(v, p, mp) + rec2(v, p, max(mp, p));
        for (auto ch : G[v]) {
            if (ch == p) continue;
            rec(ch, v, max(mp, p));
        }
    }
    else {
        res[v] = res[p] + rec2(v, p, max(mp, p));
        for (auto ch : G[v]) {
            if (ch == p) continue;
            rec(ch, v, max(mp, p));
        }
    }
}

int main() {
    cin >> N;
    G.assign(N, vector<int>());
    for (int i = 0; i < N-1; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    res.assign(N, 0);
    for (auto v : G[0]) rec(v, 0, -1);
    for (int v = 1; v < N; ++v) {
        cout << res[v];
        if (v != N-1) cout << " ";
    }
    cout << endl;
}

Measured memory_bytes: 47744
#include<bits/stdc++.h>
using namespace std;
vector<long long>num;
int main(){
 int numm,nummer,menge;
cin>>numm>>nummer;
bool erg=true;
if(numm>9||nummer>9){
	cout<<-1;
	return 0;
}
cout<<numm*nummer;

 return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <unordered_map>
#include <deque>
#include <list>
#include <set>
#include <random>
#include <deque>

using namespace std;
using ll = long long;
const int BIG = 100000007;


int main(){
    ll x,y;
    cin >> x >> y;
    ll l = y - 2 * x;
    if(l >= 0 && l <= 2 * x && l % 2 == 0){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}




Measured memory_bytes: 3132
a, b, k = map(int, input().split())
if b-a+1 < 2*k:
    for i in range(a,b+1):
        print(i)
    exit(0)
for i in range(a,a+k):
    print(i)
for i in range(b-k+1,b+1):
    print(i)

Measured memory_bytes: 3060
x,y,z,w=map(int,input().split())

t=(z-x,w-y)
u=(y-w,z-x)
l=(x-z,y-w)

x3=(z+u[0],w+u[1])
x4=(x3[0]+l[0],x3[1]+l[1])

print(x3[0],x3[1],x4[0],x4[1])


Measured memory_bytes: 3060
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
//ll mod = 998244353;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main() {
    int n, k;
    cin >> n >> k;
    map<int, int> mp;
    rep(i, n) {
        int a;
        cin >> a;
        ++mp[a];
    }
    int m = mp.size();
    if (m <= k) {
        cout << 0 << endl;
        return 0;
    }
    vector<pair<int, int>> num;
    for (auto p: mp) {
        num.emplace_back(p.second, p.first);
    }
    sort(num.begin(), num.end());
    int ans = 0;
    int idx = 0;
    while(1) {
        if (m <= k) {
            break;
        }
        else {
            ans += num[idx].first;
            --m;
        }
        ++idx;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 14736
// This file is a "Hello, world!" in C++ language by GCC for wandbox.
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int h, w, k;
    char a[6][6];
    
    cin >> h >> w >> k;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> a[j][i];
        }
    }
    
    int count = 0;
    for (int i = 0; i < (int)pow(2,h); i++) {
        for (int j = 0; j < (int)pow(2, w); j++) {
        
            int c = 0;
            for (int y = 0; y < h; y++) {
                for (int x = 0; x < w; x++) {
                    if ('#' == a[x][y] && (i & (1 << y)) != 0 && (j & (1 << x)) != 0 ) {
                        c++;
                    }
                }
            }
            if (k == c) {
                count++;
            }
        }
    }
    cout << count << endl;    
}


Measured memory_bytes: 4060
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <map>
#include <tuple>
#include <iostream>
#include <deque>
#include <array>
#include <set>
#include <functional>


int main() {
	int p, q, r; std::cin >> p >> q >> r;
	std::cout << p + q + r - std::max({ p, q, r }) << std::endl;
};

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

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

    string s;
    cin >> s;

    bool f = true;
    for(int i = 1; i < s.size(); i++){
        if(s[i] == '9');
        else{
            f = false;
            break;
        }
    }

    if(f) cout << (int)(s[0] - '0') + ((int)s.size() - 1) * 9 << endl;
    else cout << (int)(s[0] - '0') + ((int)s.size() - 1) * 9 - 1 << endl;

    return 0;
}

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

using namespace std;

#define int long long
#define FR first
#define SC second
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, f, n) for(int i = (int)(f); i < (int)(n); i++)
#define each(a, b) for(auto& a : b)

typedef pair<int, int> P;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

struct edge
{
  int to, cost;
  edge(){}
  edge(int to, int cost):to(to), cost(cost){}
};

vector< vector<edge> > graph;
vector< vector<int> > mincost;

int dijkstra(int s)
{
  priority_queue<P, vector<P>, greater<P> > que;
  que.push(P(0, s));
  mincost[s][s] = 0;
  while(!que.empty()) {
    int cost, now;
    tie(cost, now) = que.top(); que.pop();
    if(mincost[s][now] < cost) continue;
    for(edge& e : graph[now]) {
      if(e.cost + cost < mincost[s][e.to]) {
	mincost[s][e.to] = e.cost + cost;
	que.push(P(mincost[s][e.to], e.to));
      }
    }
  }
  return *max_element(all(mincost[s]));
}

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N, R;
  cin >> N >> R;
  graph.resize(N);
  rep(i, R) {
    int s, t, d;
    cin >> s >> t >> d; s--, t--;
    graph[s].emplace_back(t, d);
    graph[t].emplace_back(s, d);
  }

  mincost.resize(N, vector<int>(N, inf));
  int maxdist = 0;
  rep(i, N) maxdist = max(maxdist, dijkstra(i));

  vector<P> ep;
  rep(i, N) reps(j, i+1, N) {
    if(mincost[i][j] == maxdist) ep.emplace_back(i, j);
  }

  vector<int> ans;
  rep(i, N) {
    bool flag = true;
    for(auto& p : ep) {
      int s, t; tie(s, t) = p;
      if(mincost[s][i] + mincost[i][t] == maxdist) flag = false;
    }
    if(flag) ans.push_back(i+1);
  }
  
  cout << ans.size() << endl;
  rep(i, ans.size()) cout << ans[i] << endl;
  
  return 0;
}

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

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rep2(i,s,n) for(int i = (s); i < (n); ++i)
#define ll long long
#define ld long double
#define P pair<ll,ll>
#define all(v) v.begin(),v.end()

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1.0);

int main(void)
{
    ll n; cin>>n;
    map<ll,ll> mp;
    rep(i,n){
        ll a; cin>>a;
        if(mp[a]) ++mp[a];
        else --mp[a];
    }
    ll ans=0;
    for(auto x:mp) if(x.second) ++ans;
    cout<<ans<<endl;
    return 0;
}

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

int main(){
    int n, w;
    cin >> n >> w;
    int w1, v1;
    cin >> w1 >> v1;
    vector<int> nap1;
    vector<int> nap2;
    vector<int> nap3;
    vector<int> nap4;
    nap1.push_back(v1);
    long long w_base = w1;
    for (int i = 1; i < n; i++){
        cin >> w1 >> v1;
        if (w1 == w_base) nap1.push_back(v1);
        else if (w1 == w_base + 1) nap2.push_back(v1);
        else if (w1 == w_base + 2) nap3.push_back(v1);
        else nap4.push_back(v1);
    }
    sort(nap1.begin(), nap1.end(), greater<int>());
    sort(nap2.begin(), nap2.end(), greater<int>());
    sort(nap3.begin(), nap3.end(), greater<int>());
    sort(nap4.begin(), nap4.end(), greater<int>());
    int k1 = (int)nap1.size();
    int k2 = (int)nap2.size();
    int k3 = (int)nap3.size();
    int k4 = (int)nap4.size();
    vector<long long> acc_nap1(k1 + 1, 0);
    vector<long long> acc_nap2(k2 + 1, 0);
    vector<long long> acc_nap3(k3 + 1, 0);
    vector<long long> acc_nap4(k4 + 1, 0);
    for (int i = 0; i < k1; i++) acc_nap1[i+1] = acc_nap1[i] + nap1[i];
    for (int i = 0; i < k2; i++) acc_nap2[i+1] = acc_nap2[i] + nap2[i];
    for (int i = 0; i < k3; i++) acc_nap3[i+1] = acc_nap3[i] + nap3[i];
    for (int i = 0; i < k4; i++) acc_nap4[i+1] = acc_nap4[i] + nap4[i];

    long long ans = 0;

    for (int s1 = 0; s1 <= k1; s1++){
        for (int s2 = 0; s2 <= k2; s2++){
            for (int s3 = 0; s3 <= k3; s3++){
                for (int s4 = 0; s4 <= k4; s4++){
                    if (w_base * (s1 + s2 + s3 + s4) + s2 + s3 *2 + s4 * 3 <= w){
                        ans = max(ans, (acc_nap1[s1] + acc_nap2[s2] + acc_nap3[s3] + acc_nap4[s4]));
                    }
                }
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
def main():
    from collections import Counter
    N, P = (int(i) for i in input().split())
    S = [int(s) for s in input()]

    ans = 0
    if P == 5 or P == 2:
        for i, s in enumerate(S, start=1):
            # j文字取る
            if s % P == 0:
                ans += i
    else:
        acc = [0]*(N+1)
        d = 1
        for i, s in enumerate(S[::-1], start=1):
            # print(i, s)
            acc[i] = (s * d + acc[i-1]) % P
            d *= 10
            d %= P
        c = Counter(acc)
        # print(acc, c)
        ans = sum(v*(v-1)//2 for v in c.values())
    print(ans)


if __name__ == '__main__':
    main()


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

int main()
{
    ll n,m,ans=0,ac=0;
    cin>>n>>m;
    vector<ll> wrong(n+1,0),check(n+1,0);
    for(ll i=0;i<m;i++)
    {
        ll prob;
        string res;
        cin>>prob>>res; prob--;
        if(check[prob]==1) continue;
        if(res=="AC") check[prob]=1;
        else
        wrong[prob]++;
    }
    for(ll i=0;i<n;i++)
    {
        if(check[i]==1)
        {
            ac++;
            ans += wrong[i];
        }
    }
    cout<<ac<<" "<<ans<<endl;
}

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

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

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

#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

const int INF = (int)1e9;
const LL INFL = (LL)1e19;
const int MOD = 1e9 + 7;

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    double a, b, c, d, e;
    cin >> a >> b >> c >> d >> e;
    int ans = ceil(a/10)*10 + ceil(b/10)*10 + ceil(c/10)*10 + ceil(d/10)*10 + ceil(e/10)*10;

    ans -= max({(10 - int(a) % 10) % 10, (10 - int(b) % 10) % 10, (10 - int(c) % 10) % 10, (10 - int(d) % 10) % 10, (10 - int(e) % 10) % 10});
    cout << ans << endl;
    
}

Measured memory_bytes: 256
#include<algorithm>
#include<map>
#include<iostream>
#include<string>
#include<vector>

using namespace std;

map<string, vector<int> > ans;

int main()
{
  string s;
  int n;
  while(cin >> s >> n)
  {
    ans[s].push_back(n);
  }

  for(map<string, vector<int> >:: iterator i = ans.begin(); i != ans.end(); i++)
  {
    cout << (*i).first << endl;

    sort((*i).second.begin(), (*i).second.end());
    for(int j = 0; j < (*i).second.size() - 1; j++)
    {
      cout << (*i).second[j] << " ";
    }
    cout << (*i).second[(*i).second.size() - 1] << endl;
  }
}

Measured memory_bytes: 1244
import itertools
s = set()
N = int(input())
dict = {i:0 for i in "MARCH"}

sum_v = 0
ans = 0
for i in range(N):
    S = input()
    if(S[0] in "MARCH"):
        dict[S[0]] += 1
        s.add(S[0])
        sum_v += 1
        
c = itertools.combinations(s, 3)

for i in c:
    ans += dict[i[0]] * dict[i[1]] * dict[i[2]]
    
print(ans)

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

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    if (b > a * c)
    {
        cout << c << endl;
    }
    else
    {
        cout << b / a << endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <iterator>
#include <set>
#include <queue>
#include <bitset>
#include <cassert>

using namespace std;


int main() {

    long long a,b,c,d;
    cin>>a>>b>>c>>d;
    
    cout << max(a*c,max(b*d,max(a*d,b*c))) << endl;

    return 0;

}

Measured memory_bytes: 3616
#include <iostream>
#include <queue>
#include <string>
#include <vector>
#define INF 1000000000000000000LL
#define MP(a,b,c) make_pair(a,make_pair(b,c))
using namespace std;
typedef long long ll;
typedef pair <ll,pair<int,int> > P;
int h,w,n;
ll mp[1010][1010],D[1010][1010];
bool visited[1010][1010];
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};

void mk_mp(int x,int y,int t,string str){
  mp[y][x]++;
  while(t--)
    for(int i=0;i<(int)str.size();i++){
      int j=0;//D
      if(str[i]=='U')j=1;
      if(str[i]=='L')j=2;
      if(str[i]=='R')j=3;
      int nx=x+2*dx[j],ny=y+2*dy[j];
      if(nx<1||ny<1||nx>=2*w||ny>=2*h)continue;
      x=nx,y=ny;
      mp[y][x]++;
      mp[y-dy[j]][x-dx[j]]++;
    }  
}

ll dijkstra(int x,int y,int gx,int gy){
  for(int i=0;i<1010;i++)
    for(int j=0;j<=1010;j++) D[i][j]=INF;
  priority_queue <P,vector<P>,greater<P> > Q;
  Q.push(MP(0,x,y));
  D[y][x]=0;
  while(!Q.empty()){
    ll dis=Q.top().first;
    int x=Q.top().second.first;
    int y=Q.top().second.second;
    Q.pop();
    if(x==gx&&y==gy)return dis;
    if(visited[y][x]==1)continue;
    visited[y][x]=1;  
    for(int i=0;i<4;i++){
      int nx=x+dx[i],ny=y+dy[i];
      if(nx<0||ny<0||nx>2*w||ny>2*h||D[ny][nx]<=dis+mp[ny][nx])continue;
      Q.push(MP(dis+mp[ny][nx],nx+dx[i],ny+dy[i]));
      D[ny][nx]=dis+mp[ny][nx];
    }
  }
  return -1;
}

int main() {
  int sx,sy,gx,gy;
  cin>>w>>h>>n;
  cin>>sx>>sy>>gx>>gy;
  for(int i=0;i<n;i++){
    int x,y,t;
    string str;
    cin>>x>>y;
    cin>>t>>str;
    mk_mp(2*x+1,2*y+1,t,str);
  }
  cout << dijkstra(2*sx,2*sy,2*gx,2*gy)<<endl;
  return 0;
}

Measured memory_bytes: 22168
A = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
N = int(input())
S = list(input())
list = list(A)
result_list = []
for i in range(len(S)):
    for ie in range(len(list)):
        if S[i] == list[ie]:
             result_list.append(list[(ie + N) % 26])
print(''.join(result_list))


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

int main()
{
  int n;
  for(;cin>>n,n;)
    {
      int sum=0;
      for(int i=0;i<n;i++)
	{
	  int x,y,h,w;
	  cin>>x>>y>>h>>w;
	  int size=x+y+h;
	  if(size<61&&w<3)
	    sum+=600;
	  else if(size<81&&w<6)
	    sum+=800;
	  else if(size<101&&w<11)
	    sum+=1000;
	  else if(size<121&&w<16)
	    sum+=1200;
	  else if(size<141&&w<21)
	    sum+=1400;
	  else if(size<161&&w<26)
	    sum+=1600;
	}
      cout<<sum<<endl;
    }
}

Measured memory_bytes: 1160
def main():
    n = int(input())
    V = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]
    ans = 0
    
    for v, c in zip(V, C):
        if v - c > 0:
            ans += v - c
        else:
            ans += 0
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 9124
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define ff first
#define ss second
 
const int N=2e5+5;
const int mod=1e9+7;
 
int binpow(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1LL)
            res = res * a;
        a = a * a;
        b >>= 1LL;
    }
    return res;
}
 
int32_t main()
{
    IOS;
    
    int n;
    cin>>n;
    string str;
    cin>>str;
    int k=str.size();
    if(k<=n)
        cout<<str;
    else
    {
        for(int i=0;i<n;i++)
            cout<<str[i];
        cout<<"...";    
    }
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vpll vector < pair<long long,long long> >
#define fill(a,val)  memset(a,val, sizeof (a))
#define sort_unique(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define all(cont) cont.begin(), cont.end()
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MAX   1e9
#define MIN  -1e9
typedef map<int,int> mpi;
typedef set<int> seti;
typedef multiset<int> mseti;
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define rep(i, n)    for(long long int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define repn(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define trav(a, x) for(auto& a : x)
struct Interval {int start, end;};
bool compare(Interval i1, Interval i2) {return (i1.start < i2.start);}
ll dp[101][100002];
int main()
{
    fio;
    ll n,W;
    cin>>n>>W;
    fill(dp,0);
    ll w[n+1],v[n+1];
    repA(i,1,n)
    cin>>w[i]>>v[i];
    rep(i,n+1)
    dp[i][0]=0;
    repA(i,1,n)
    {
        repA(j,1,W)
        {
            if(j>=w[i])
                dp[i][j]=max(v[i]+dp[i-1][j-w[i]],dp[i-1][j]);
            else
                dp[i][j]=dp[i-1][j];
        }
    }
    cout<<dp[n][W];
    return 0;
}


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

int main()
{
    char a, b; cin >> a >> b;
    cout << ((a < b) ? string((int)(b - '0'), a) : string((int)(a - '0'), b)) << endl;
}


Measured memory_bytes: 256
N,K=map(int,input().split())
OK=0
NG=K+1

while NG-OK>1:
    #print(OK,NG)
    mid=(OK+NG)//2
    ANS=0
    money=mid

    for i in range(N):
        ANS+=money
        money//=2
        if money==0:
            break

    if ANS<=K:
        OK=mid
    else:
        NG=mid
print(OK)


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

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rep2(i,s,n) for(int i = (s); i < (n); ++i)
#define ll long long
#define P pair<ll,ll>
#define all(v) v.begin(),v.end()
const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1.0);

int main(void)
{
    while(1){
        string s; cin>>s;
        if(s=="-") break;
        ll m; cin>>m;
        rep(i,m){
            ll h; cin>>h;
            string tmp;
            tmp+=s.substr(h,s.size());
            tmp+=s.substr(0,h);
            s=tmp;
        }
        cout<<s<<endl;
    }
    return 0;
}


Measured memory_bytes: 3228
#include<iostream>
#include<string>
using namespace std;
int main(){
	
	int x, y, z, a = 0;
	cin >> x >> y >> z;
	a = x;
	for (int i = 0; i < x; i++){
		a -= z;
		a -= y;
		if (a < z){
			cout << i << endl;
			break;
		}
	}


	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long int
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pii pair<int,int>
#define vvi vector<vector<int>>
#define vi vector<int>
#define f first 
#define s second 
using namespace std;
const int N=5e6+10;
const int mod=1e9+7;
int arr[N],iarr[N];
int logi(int n){int p=0;while(n/2){n=n/2;p++;}return p;}
int poww(int x,int y){int pro=1;while(y){if(y&1)pro=((pro%mod)*(x%mod)%mod);y=y>>1;x=((x%mod)*(x%mod)%mod);}return pro;}
int poww2(int x,int y){int pro=1;while(y){if(y&1)pro=pro*x;y=y>>1;x=x*x;}return pro;}
double poww1(double x,int y){double pro=1.000000000;while(y){if(y&1)pro=((pro)*(x));y=y>>1;x=((x)*(x));}return pro;}
map<int,int> mp1,mp2;
set<int> st;
int arr1[1000001],arr2[1000001];
/*

*/
void solve()
{
	int n,d,cnt=0;
	cin>>n>>d;
	for(int i=0;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		int dist = ceil(sqrt(pow(x,2)+pow(y,2)));
		if(dist<=d) cnt++;
	}
	cout<<cnt;
}

int32_t main()																																	
{
	fast;
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}


Measured memory_bytes: 3744
#include <stdio.h>
#include <string>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;

int a, b, t, r;

int main() {
    scanf("%d %d %d", &a, &b, &t);
    r = b * int((t + 0.5) / a);
    printf("%d\n", r);
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define N 1000005
#define ll long long int 	
#define MP make_pair
#define pb push_back
#define ppb pop_back
#define sp " "
#define endl "\n"
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll>
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define fast2 freopen ("myfile.in","r",stdin);freopen ("myfile.out","w",stdout);
#define mod 1000000007
#define fs(x,y) for(int i=1;i<=y;i++) cin>>x[i]
#define fo(i,x,y) for(int i=x;i<=y;i++)
using namespace std;

ll n,m,ar[N],sum,a,b;

char s[N];

int main()
{
	fast;
	cin>>s+1;
	n=strlen(s+1);
	fo(i,1,n)
		if((s[i]=='1' && i%2==0) || (s[i]=='0' && i%2==1))
			a++;
	fo(i,1,n)
		if((s[i]=='1' && i%2==1) || (s[i]=='0' && i%2==0))
			b++;
	cout<<min(a,b);

}

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

int main(){
  int n,m,c=0;
  cin>>n>>m;
  char a[50][50]={};
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      cin>>a[i][j];
    }
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      if(a[i][j]=='#'){
        cout<<"#";
        continue;
      }
      c=0;
      if(i>=1&&j>=1){
      c+=(a[i-1][j-1]=='#');
      }
      if(j>=1){
      c+=(a[i][j-1]=='#');
        if(i<49){
      c+=(a[i+1][j-1]=='#');
        }
      }
      if(i>=1){
      c+=(a[i-1][j]=='#');
      }
      if(i<49){
      c+=(a[i+1][j]=='#');
      }
      if(j<49){
        if(i<49){
      c+=(a[i+1][j+1]=='#');
        }
      c+=(a[i][j+1]=='#');
        if(i>=1){
      c+=(a[i-1][j+1]=='#');
        }
      }
      cout<<c;
    }
    cout<<endl;
  }
}


Measured memory_bytes: 256
N = int(input())
a = list(map(int, input().split()))

now = 0
s = 1

ans = 0

while now != N:
    
    if s != a[now]:
        ans += 1
    else:
        s += 1
    
    now += 1

if ans == N:
    print(-1)
else:
    print(ans)

Measured memory_bytes: 26268
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long int a,b,c,d;
  cin>>a>>b>>c;
  d=c-a-b;
  if(d>0 && d*d>4*a*b)cout<<"Yes\n";
  else cout<<"No\n";
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
#define pb push_back
template<class T>void chmax(T &a,T b){if(a<b)a=b;}
template<class T>void chmin(T &a,T b){if(a>b)a=b;}
constexpr int INF=1000000000000000000;
constexpr int mod=1000000007;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
bool prime(int a){
    if(a==1)return false;
    for(int i=2;i*i<=a;i++){
        if(a%i==0)return false;
    }
    return true;
}
vector<int>kaijo;
void init_fact(int n){
    kaijo.resize(n+1);
    kaijo[0]=1;
    for(int i=1;i<=n;i++){
        kaijo[i]=kaijo[i-1]*i;
        kaijo[i]%=mod;
    }
}
int modpow(int a,int b){
    if(b==0)return 1;
    if(b%2)return modpow(a,b-1)*a%mod;
    int memo=modpow(a,b/2);
    return memo*memo%mod;
}
int comb(int a,int b){
    //if(!kaijo[0])init_fact(2000010);
    return kaijo[a]*modpow(kaijo[a-b],mod-2)%mod*modpow(kaijo[b],mod-2)%mod;
}
int inv(int x){
    x=modpow(x,mod-2);
    return x;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){
    double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
    double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
    double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
    double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
    return tc*td<0&&ta*tb<0;
}
int n,a[200010];
map<int,int>mp;
signed main(){
    cin>>n;
    rep(i,n)cin>>a[i];
    mp[a[0]]++;
    int ans=0;
    for(int i=1;i<n;i++){
        ans+=mp[i-a[i]];
        mp[i+a[i]]++;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 27932
# N, M = gets.chomp.split.map(&:to_i)
# T = gets.chomp.chars
N = gets.chomp.to_i
works = []
N.times do 
  a, b = gets.chomp.split.map(&:to_i)
  works << [b, a]
end

works.sort!
# p works

ans = true
consumed = 0
works.each do |(b, a)|
  consumed += a
  # p consumed
  # p b
  if (consumed <= b)
    # ok
  else
    ans = false
    break
  end
end

if ans
  print "Yes\n"
else
  print "No\n"
end

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

const int N = 1e5+15;
#define ll long long

ll pre[N], suf[N];

ll sum[N];

int getValue(int i){
	return sum[i] - sum[i-1];
}
void solve(){
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i){
		int a;
		scanf("%d",&a);
		sum[i] = sum[i-1] + a;
		pre[i] = pre[i-1] + max(0,a);
	}
	for(int i=n;i>=1;--i){
		int a = getValue(i);
		suf[i] = suf[i+1] + max(0,a);
	}
	ll ret = 0;
	for(int i=1;i+k-1<=n;++i){
		ll val = max(0LL, sum[i+k-1] - sum[i-1]) + pre[i-1] + suf[i+k];
		ret = max(ret,val);
	}
	printf("%lld\n", ret);
}
int main(){
	//freopen("input.txt","r",stdin);
	solve();
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
  string S,T;
  int Q;
  cin>>S>>T>>Q;
  int N=S.size(),M=T.size();
  vector<int> A(N+1),B(M+1);
  for(int i=0;i<N;i++)A[i+1]=A[i]+(S[i]=='A'?1:2);
  for(int i=0;i<M;i++)B[i+1]=B[i]+(T[i]=='A'?1:2);
  while(Q--){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    if((A[b]-A[a-1])%3==(B[d]-B[c-1])%3)puts("YES");
    else puts("NO");
  }
}

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

#define pb push_back
//#define ll unsigned long long
/*int main(){
  ll n ;
  cin >> n ;

  ll sum1=0;
  while(n!=0){
    int b= sum1%10;
    sum1+=b;
    n=n/10;
  }
  if(sum1%9==0){
    cout <<"Yes"<<"\n";
  }
  else {
    cout <<"No"<<"\n";
  }
  return 0;
}
*/

//stroing into a form of string

int check(string str){
  int n =str.length();
  int digSum=0;
  for(int i=0;i<n;i++){
    digSum += (str[i]-'0');
  }
  return (digSum%9 ==0);
}


int main(){
  string n ;
  cin >> n ;
  check(n) ?cout <<"Yes":cout <<"No"<<"\n";

  return 0;
}


Measured memory_bytes: 3776
#include <algorithm>
#include <cmath>
#include <iostream>
#include <numeric>
#include <string>
#include <string.h>
#include <vector>

#define REP(i,x) for(int i{ 0 }; i < (int)(x); i++)
#define REPC(i,x) for(int i{ 0 }; i <= (int)(x); i++)
#define RREP(i,x) for(int i{ (int)(x) - 1 }; i >= 0 ;i--)
#define RREPC(i,x) for(int i{ (int)(x)}; i > 0; i--)
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef int64_t int64;

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

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


class C {
	int n, k;
	vector<int> left, right;
public:
	C()
	{
		cin >> n >> k;
		int tmp;
		REP(i, n)
		{
			cin >> tmp;
			if (tmp < 0)
				left.PB( -tmp);
			else
				right.PB(tmp);
		}
		sort(ALL(left));
	}
	void solve()
	{
		int ans{ (pow(10, 9)) };
		int cost_left, cost_right, use_right;
		int n_items_left{ SZ(left) }, n_items_right{ SZ(right) };

		if (n_items_right >= k)
			ans = right[k - 1];

		if (n_items_left >= 1)
		{
			REP(i, n_items_left)
			{

				use_right = k - i - 1;
				if (use_right > n_items_right)
					continue;

				if (use_right == 0)
				{
					chmin(ans, left[k - 1]);
					break;
				}

				if (i + 1 > k)
					break;

				cost_left = left[i];
				cost_right = right[use_right - 1];

				chmin(ans, 2 * cost_left + cost_right);
				chmin(ans, cost_left + 2 * cost_right);
			}
		}

		cout << ans << endl;

	}
};


int main()
{
	C solution;
	solution.solve();

	return 0;
}

Measured memory_bytes: 1020
while True:
    a,b=map(int,input().split())
    if a==0 and b==0:
        break
    
    if a<b:
        a,b=b,a
        
    sum=0
    while b>0:
        a=a%b
        a,b=b,a
        sum+=1
        
    print(a,sum)


Measured memory_bytes: 5612
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 210000;
long long fact[C_SIZE];
long long finv[C_SIZE];
long long inv[C_SIZE];
long long C(int a,int b){
	if(a<b||b<0)return 0;
	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
void init_C(int n){
	fact[0]=finv[0]=inv[1]=1;
	for(int i=2;i<n;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=1;i<n;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
}
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
// ここから編集しろ
vector<int>g[110000];
long long ks=1;
int K;
void dfs(int a,int b,int c){
	ks=ks*max(0,c)%mod;
	int cnt=0;
	int nx=K-1;
	if(b!=-1)nx--;
	for(int i=0;i<g[a].size();i++){
		if(b==g[a][i])continue;
		dfs(g[a][i],a,nx);
		nx--;
	}

}
int main(){
	init_C(110000);
	int a,b;scanf("%d%d",&a,&b);
	K=b;
	for(int i=0;i<a-1;i++){
		int p,q;scanf("%d%d",&p,&q);
		p--;q--;
		g[p].push_back(q);
		g[q].push_back(p);
	}
	dfs(0,-1,b);
	printf("%lld\n",ks);
}

Measured memory_bytes: 14720
def make_2dgrid(g)
    h = g.size
    s = Array.new(h + 1) { Array.new(h + 1, 0) }
    h.times do |i|
      h.times do |j|
        s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + g[i][j]
      end
    end
    s
  end
   
  def query(s, x1, x2, y1, y2)
    s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1]
  end
   
  n, k = gets.split.map(&:to_i)
   
  k2 = 2 * k
  gB = Array.new(k2) { Array.new(k2, 0) }
  n.times do
    x, y, ci = gets.split
    x = x.to_i % k2
    y = (y.to_i + (ci == "W" ? k : 0)) % k2
    gB[x][y] += 1
  end
  ans = 0
   
  sB = make_2dgrid(gB)
   
  sBk2 = sB[k2]
  sB0 = sB[0]
  score1 = sB0[0] - sB0[k2] - sBk2[0] + sBk2[k2] 

  sBk2diff_sB0diff=k.times.map{|i| sBk2[i]-sBk2[i+k]-sB0[i]+sB0[i+k]}

  k.times do |i|
    sBi = sB[i]
    sBik = sB[i + k]
    score2 = score1 + sBik[0] - sBik[k2] - sBi[0] + sBi[k2]
    k.times do |j|
      score3 = score2 + 2 * (sBi[j] - sBi[j + k] - sBik[j] + sBik[j + k]) + sBk2diff_sB0diff[j]
      nmscore3 = n - score3
      ans = score3 if ans < score3
      ans = nmscore3 if ans < nmscore3
    end
  end
  p ans


Measured memory_bytes: 66812
use std::io;

fn main() {
    let mut line = String::new();
    io::stdin().read_line(&mut line).unwrap();
    let mut iter = line.split_whitespace().map(|s| s.parse::<i32>().unwrap());
    let (w, h, x, y, r) = (
        iter.next().unwrap(), iter.next().unwrap(), iter.next().unwrap(),
        iter.next().unwrap(), iter.next().unwrap(),
    );
    if x - r >= 0 && x + r <= w && y - r >= 0 && y + r <= h {
        println!("Yes");
    } else {
        println!("No");
    }
}



Measured memory_bytes: 5032
N,M,C = map(int, input().split())
B = list(map(int,input().split()))
ans = 0
for i in range(N):
  A = list(map(int,input().split()))
  sum = 0
  for j in range(M):
    sum += A[j] * B[j]
  if sum > -C:
    ans += 1
print(ans)
      

Measured memory_bytes: 9136
#include <cstdio>
#include <cstring>
#include <algorithm>

typedef long long LL;
const int Mod = 1000000007;
const int MN = 505;

inline void Add(int &x, int y) { x -= (x += y) >= Mod ? Mod : 0; }
inline int qPow(int b, int e) {
	int a = 1;
	for (; e; e >>= 1, b = (LL)b * b % Mod)
		if (e & 1) a = (LL)a * b % Mod;
	return a;
}

int N, b[MN];
int Fac[MN], iFac[MN];
int Pow[MN][MN];

inline void Init() {
	int M;
	scanf("%d%d", &M, &N);
	for (int x; M--; ) scanf("%d", &x), ++b[x];
	
	Fac[0] = 1;
	for (int i = 1; i <= N + 1; ++i) Fac[i] = (LL)Fac[i - 1] * i % Mod;
	iFac[N + 1] = qPow(Fac[N + 1], Mod - 2);
	for (int i = N + 1; i >= 1; --i) iFac[i - 1] = (LL)iFac[i] * i % Mod;
	
	for (int i = 0; i <= N + 1; ++i)
		for (int j = 0; j <= 501; ++j)
			Pow[i][j] = qPow(i, j);
}

int f[MN][MN], g[MN][MN]; // [sum][cnt]
inline int DP() {
	int Ans = 0;
	f[0][0] = 1;
	for (int i = N; i >= 1; --i) {
//		printf("\t\ttrans : (%d) to (%d)\n", i + 1, i);
		memset(g, 0, sizeof g);
		for (int sum = 0; sum <= N; ++sum) {
			for (int cnt = 0; sum + (i + 1) * cnt <= N + 1; ++cnt) {
				for (int num = 0; sum + (i + 1) * (cnt + num) <= N + 1; ++num) {
					if (!f[sum][cnt]) continue;
					// f[sum][cnt] -> g[sum + cnt + num][cnt + num]
//					printf("f[%d][%d] -> g[%d][%d] (num = %d)\n", sum, cnt, sum + cnt + num, cnt + num, num);
					Add(g[sum + cnt + num][cnt + num], (LL)f[sum][cnt] * iFac[num] % Mod);
				}
			}
		}
		for (int sum = 0; sum <= N; ++sum) {
			for (int cnt = 0; sum + i * cnt <= N + 1; ++cnt) {
				if (!g[sum][cnt]) continue;
				g[sum][cnt] = (LL)g[sum][cnt] * Pow[sum][b[i]] % Mod;
//				printf("g[%d][%d] = %d = %lld / 518400\n", sum, cnt, g[sum][cnt], (LL)g[sum][cnt] * 518400 % Mod);
			}
		}
		std::swap(f, g);
	}
//	puts("Calc");
	for (int sum = 0; sum <= N; ++sum) {
		for (int cnt = 0; sum + cnt <= N + 1; ++cnt) {
			if (!f[sum][cnt]) continue;
//			printf("f[%d][%d] = %d = %lld / 518400\n", sum, cnt, f[sum][cnt], (LL)f[sum][cnt] * 518400 % Mod);
			Ans = (Ans + (LL)((N - sum) & 1 ? Mod - 1 : 1) * Fac[N + 1 - sum] % Mod * iFac[N + 1 - sum - cnt] % Mod * f[sum][cnt]) % Mod;
		}
	}
	return Ans;
}

int main() {
	Init();
	printf("%d\n", DP());
	return 0;
}

Measured memory_bytes: 3200
#include <iostream>

using namespace std;

int main(void){
  int a, b;
  cin >> a >> b;

  int i;
  if(b<a)
    for(i=0; i<a; i++)
      cout << b;
  else
    for(i=0; i<b; i++)
      cout << a;

  cout << endl;
  
  return 0;
}


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

int ways[11];

int main()
{
loop:
  int n, m;
  for(int i = 0; i < 11; i++)
    ways[i] = 0;
  cin >> n >> m;
  if(!n)
    return 0;
  for(int i = 0; i < n; i++)
  {
    int d, p;
    cin >> d >> p;
    ways[p] += d;
  }
  for(int i = 10; i > 0; i--)
  {
    if(ways[i] < m)
    {
      m -= ways[i];
      ways[i] = 0;
    }
    else
    {
      ways[i] -= m;
      m = 0;
    }
  }
  int ans = 0;
  for(int i = 1; i <= 10; i++)
    ans += ways[i] * i;
  cout << ans << endl;
  goto loop;
}

Measured memory_bytes: 1160