akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <string>
#include <map>
using namespace std;
typedef long long int ll;
const ll MOD = 1000000007LL;
map<pair<ll,ll>, ll> um;

ll func(ll s, ll x){
  	//cout << s << ":" << x << endl;
  	if(s==0) return 1;
    //ch(s,x);
    if(um.find(make_pair(s,x))!=um.end()) return um[make_pair(s,x)];
    ll ret=0;
        ret += func(s/2, x/2);
        if(s>0&&x>0)ret += func( (s-1) / 2,(x - 1) / 2); 
  		ret %= MOD;
        if(s>1)ret += func( (s-2) / 2, x/2);
    um[make_pair(s,x)] = ret % MOD;
    return (ret % MOD);
}

int main(){
    ll n;
    cin >> n;
    cout << func(n,n) << endl;
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Program
{
    static void Main(string[] args)
    {
        var N = Int32.Parse(Console.ReadLine());
        var A = Console.ReadLine().Split(' ').Select(__ => Int32.Parse(__)).ToArray();
        var B = Console.ReadLine().Split(' ').Select(__ => Int32.Parse(__)).ToArray();

        var count = 0L;
        for (var i = 0; i < N; i++)
        {
            var a = Math.Min(A[i], B[i]);
            count += a;
            A[i] -= a;
            B[i] -= a;

            a = Math.Min(A[i+1], B[i]);
            count += a;
            A[i+1] -= a;
            B[i] -= a;
        }

        Console.WriteLine(count);
        
    }
}



Measured memory_bytes: 38428
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define db double
#define pint pair<int,ll>
#define mk make_pair
#define pb push_back
#define eb emplace_back
#define ins insert
#define fi first
#define se second
#define Rep(x,y,z) for(int x=y;x<=z;x++)
#define Red(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
const int MAXN=105;
char buf[1<<12],*pp1=buf,*pp2=buf,nc;int ny;
inline char gc() {return pp1==pp2&&(pp2=(pp1=buf)+fread(buf,1,1<<12,stdin),pp1==pp2)?EOF:*pp1++;}
//inline char gc(){return getchar();}
inline int read(){
	int x=0;for(ny=1;nc=gc(),(nc<48||nc>57)&&nc!=EOF;)if(nc==45)ny=-1;if(nc<0)return nc;
	for(x=nc-48;nc=gc(),47<nc&&nc<58&&nc!=EOF;x=(x<<3)+(x<<1)+(nc^48));return x*ny;
}
int n,m,a[MAXN];
int main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	n=read(),m=read();int cnt=0,p1=0,p2=0;
	Rep(i,1,m)a[i]=read(),cnt+=a[i]&1;
	if(cnt>2)return puts("Impossible"),0;
	Rep(i,1,m)if(a[i]&1)if(p1)p2=i;else p1=i;
	if(cnt>=1)swap(a[1],a[p1]);if(cnt>=2)swap(a[m],a[p2]);
	Rep(i,1,m)cout<<a[i]<<" ";cout<<'\n';
	if(n==1)return puts("1\n1"),0;
	if(m==1)return cout<<"2\n1 "<<n-1,0;
	a[1]--,a[m]++;cout<<m-(!a[1])<<'\n';
	Rep(i,a[1]?1:2,m)cout<<a[i]<<' ';cout<<'\n';
	return 0;
}




Measured memory_bytes: 3640
#include <iostream>
#include <map>

int n, m;

int search(std::map<int, std::map<int, bool> > *nodes, std::map<int, bool> *a, int k) {
    int count = 0;
    int i = 0;
    for (std::map<int, bool>::iterator j = (*a).begin(); j != (*a).end(); ++j) {
        if (j->second) {
            i++;
        } else {
            break;
        }
    }
    if (i == n) {
        return 1;
    }
    for (std::map<int, bool>::iterator j = (*nodes)[k].begin(); j != (*nodes)[k].end(); ++j) {
        if (!j->second && !(*a)[j->first]) {
            std::map<int, std::map<int, bool> > b = *nodes;
            std::map<int, bool> c = *a;
            b[k][j->first] = true;
            b[j->first][k] = true;
            c[j->first] = !c[j->first];
            count += search(&b, &c, j->first);
        }
    }
    return count;
}

int main() {
    std::cin >> n >> m;
    std::map<int, std::map<int, bool> > nodes;
    std::map<int, bool> a;
    for (int i = 0; i < m; i++) {
        int a, b;
        std::cin >> a >> b;
        nodes[a][b] = false;
        nodes[b][a] = false;
    }
    a[1] = true;
    int c = search(&nodes, &a, 1);
    std::cout << c << std::endl;
}

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

int n, m;
bool flag;
vector<int> a;

void recSearch(int sum, int i) {
	if (i == n) {
		if (sum == m) flag = true;
		return;
	}
	sum += a[i];
	recSearch(sum, i + 1);
	sum -= a[i];
	recSearch(sum, i + 1);
}

signed main() {
	int q;
	cin >> n;
	a.resize(n);
	for (auto &e : a) cin >> e;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		cin >> m;
		flag = false;
		recSearch(0, 0);
		if (flag) cout << "yes" << endl;
		else cout << "no" << endl;
	}
}



Measured memory_bytes: 3128
#include<iostream>
#include<iomanip>
#include<string>
#include<algorithm>
#include<vector>
#include<utility>
#include<tuple>
#include<map>
#include<queue>
#include<stack>
#include<deque>
#include<bitset>
#include<math.h>
using namespace std;
using ll = int64_t;
using Graph = vector<vector<int> >;
const ll M = 1000000007;

int point(char a,int r,int s,int p){
    if(a=='r') return p;
    if(a=='s') return r;
    if(a=='p') return s;
    return 0;
}

int main(){
    int n,k,r,s,p;
    cin >> n >> k >> r >> s >> p;
    string t;
    cin >> t;

    int m = n/k +1;
    vector<vector<char> > h(m,vector<char>(k,'x'));

    for(int i=0;i<m;i++){
        for(int j=0;j<k;j++){
            if(i*k+j>=n) break;
            h.at(i).at(j)=t.at(i*k+j);
        }
    }

    /*cout << endl;
    for(int i=0;i<m;i++){
        for(int j=0;j<k;j++){
            cout << h.at(i).at(j) << " ";
        }
        cout << endl;
    }
    cout << endl;*/

    int sum[k];
    for(int i=0;i<k;i++) sum[i]=0;

    for(int i=0;i<k;i++){
        int ser=0;
        sum[i]+=point(h.at(0).at(i),r,s,p);
        for(int j=1;j<m;j++){
            if(h.at(j).at(i)=='x') break;

            if(h.at(j-1).at(i)==h.at(j).at(i)){
                ser++;
                if(ser%2==0) sum[i]+=point(h.at(j).at(i),r,s,p);
            }else{
                ser=0;
                sum[i]+=point(h.at(j).at(i),r,s,p);
            }
        }
    }

    /*cout << endl;
    for(int i=0;i<k;i++) cout << sum[i] << endl;
    cout << endl;*/
    
    int sumsum=0;
    for(int i=0;i<k;i++) sumsum+=sum[i];

    cout << sumsum << endl;
}

Measured memory_bytes: 8720
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef pair<int,string> P;
P v[22];
vector<int> d[33];
int main(void){
  int n;
  while(cin >> n && n){
    int m;
    for(int i = 0; i < 33; i++) d[i].clear();
    for(int i = 0; i < n; i++){
      v[i].first = 0;
      cin >> v[i].second >> m;
      for(int j = 0; j < m; j++){
	int a;
	cin >> a;
	v[i].first += n - (int)d[a].size();
	for(int k = 0; k < (int)d[a].size(); k++){
	  v[d[a][k]].first--;
	}
	d[a].push_back(i);
      }
    }
    sort(v,v+n);
    cout << v[0].first << " " << v[0].second << endl;
  }
}

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

/* 大文字を小文字に変換 */
char tolower(char c) {return (c + 0x20);}
/* 小文字を大文字に変換 */
char toupr(char c) {return (c - 0x20);}

// if('A'<=s[i] && s[i]<='Z') s[i] += 'a'-'A';

/*
string s = "abcdefg"
s.substr(4) "efg"
s.substr(0,3) "abc"
s.substr(2,4) "cdef"

// イテレータ要素のインデックス
distance(A.begin(), itr);
*/

struct DisjointSet{
    vector<ll> p;
    DisjointSet(ll n) : p(n){
        rep(i,n) p[i] = -1;
    }

    ll root(ll x){
        if(p[x] < 0) return x;
        return p[x] = root(p[x]);
    }

    void unite(ll x, ll y){
        ll rx = root(x);
        ll ry = root(y);
        if(rx == ry) return;
        p[ry] = rx;
    }

    bool same(ll x, ll y){
        ll rx = root(x);
        ll ry = root(y);
        return rx == ry;
    }
};


int main()
{
    ll n; cin >> n;
    vector<tuple<ll, ll, ll> > sortx;
    vector<tuple<ll, ll, ll> > sorty;
    rep(i,n){
        ll x, y; cin >> x >> y;
        sortx.push_back(make_tuple(x, y, i));
        sorty.push_back(make_tuple(y, x, i));
    }
    // cout << "ok" << endl;
    sort(sortx.begin(), sortx.end());
    sort(sorty.begin(), sorty.end());

    vector<tuple<ll, ll, ll> > eds;
    // cout << "ok2" << endl;
    rep(i,n-1){
        ll x_i0, y_i0, i0;
        ll x_i1, y_i1, i1;
        tie(x_i0, y_i0, i0) = sortx[i];
        tie(x_i1, y_i1, i1) = sortx[i+1];
        eds.push_back(make_tuple(x_i1-x_i0, i0, i1));
        tie(y_i0, x_i0, i0) = sorty[i];
        tie(y_i1, x_i1, i1) = sorty[i+1];
        eds.push_back(make_tuple(y_i1-y_i0, i0, i1));
    }
    // cout << "ok3" << endl;
    sort(eds.begin(), eds.end());

    ll size_eds = eds.size();

    DisjointSet dis = DisjointSet(n);
    // cout << "ok4" << endl;
    ll ans = 0;

    rep(i,size_eds){
        ll w, s, t;
        tie(w, s, t) = eds[i];
        if(!dis.same(s, t)){
            ans += w;
            dis.unite(s, t);
        }
    }
    // cout << "ok5" << endl;
    cout << ans << endl;
}

Measured memory_bytes: 14256
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int n = Integer.parseInt(sa[0]);
		int a = Integer.parseInt(sa[1]);
		int b = Integer.parseInt(sa[2]);
		sa = br.readLine().split(" ");
		int[] x = new int[n];
		for (int i = 0; i < n; i++) {
			x[i] = Integer.parseInt(sa[i]);
		}
		br.close();

		long ans = 0;
		for (int i = 1; i < n; i++) {
			long c = x[i] - x[i - 1];
			c *= a;
			ans += c < b ? c : b;
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 37900
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args)throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder print=new StringBuilder();
        int n=Integer.parseInt(br.readLine());
        int mod=1000000007;
        long dp[]=new long[n+1];
        dp[0]=1;
        for(int i=3;i<=n;i++){
            for(int j=3;j<=i;j++){
                dp[i]=(dp[i]+dp[i-j])%mod;
            }
        }
        System.out.println(dp[n]);
    }
}


Measured memory_bytes: 25796
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define debug(x) cerr<<#x<<": "<<x<<endl
#define sz(x) (int)(x).size()
#define trav(a,x) for(auto &a:x)
#define all(x) x.begin(), x.end()
using ll = long long;
bool solve(vector<bool> a) {
    int n= sz(a);
    rep(i,0,22) {
        if((n-1)>>i&1) {
            int d =1<<i;
            rep(j,0,n) if(j+d<n) {
                a[j]=a[j]!=a[j+d];
            }
        }
    }
    return a[0];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // string t;
    // cin>>t;
    // vector<bool> x(sz(t));
    // rep(i,0,sz(t)) x[i]=t[i]=='1';
    // debug(solve(x));
    // return 0;
    int n;
    cin>>n;
    string s;
    cin>>s;
    --n;
    vector<int> a(n);
    rep(i,0,n) a[i]=abs(s[i+1]-s[i]);
    vector<bool> one(n), two(n);
    rep(i,0,n) {
        one[i]=a[i]==1;
        two[i]=a[i]==2;
    }
    bool anyone=false;
    rep(i,0,n) if(a[i]==1) anyone=true;
    int ans=0;
    if(anyone) {
        if(solve(one)) ans=1;
    }
    else if(solve(two)) ans=2;
    cout<<ans<<endl;

}


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

int main()
{
    ll n,k;
    cin>>n>>k;
    ll r,s,p;
    cin>>r>>s>>p;
    string ss;
    cin>>ss;string arr[k];
    for(int i=0;i<n;i++)
        arr[i%k]+=ss[i];
    ll sum=0;
    for(int i=0;i<k;i++){
        ll m=arr[i].length();
        ll dp[m][3];
        dp[0][1]=0;dp[0][0]=0;dp[0][2]=0;
        if(arr[i][0]=='r')dp[0][1]+=p;
        else if(arr[i][0]=='p')dp[0][2]+=s;
        else if(arr[i][0]=='s')dp[0][0]+=r;
        for(int j=1;j<m;j++)
        {
            dp[j][0]=max(dp[j-1][1],dp[j-1][2]);
            dp[j][1]=max(dp[j-1][0],dp[j-1][2]);
            dp[j][2]=max(dp[j-1][0],dp[j-1][1]);
            if(arr[i][j]=='r'&& arr[i][j-1]!='r')
                dp[j][1]+=p;
            else if(arr[i][j]=='p' && arr[i][j-1]!='p')
                dp[j][2]+=s;
            else if(arr[i][j]=='s' && arr[i][j-1]!='s')
                dp[j][0]+=r;
            arr[i][j]='a';
        }
        sum+=max(dp[m-1][0],max(dp[m-1][1],dp[m-1][2]));
    }
    cout<<sum;
}


Measured memory_bytes: 5120
#include <stdio.h>

int main(void){

	int n;
	int i,j,k;
	scanf("%d", &n);
	
	char suit[n];
	int num[n];
	char suitlib[]="SHCD";
	char space;
	int exist;
	
	for(i=0;i<n;i++){
		scanf("\n%c",&suit[i]);
		scanf("%c",&space);
		scanf("%d",&num[i]);
	}

	for(j=0;j<4;j++){
		for(k=1;k<14;k++){
			exist=1;
			for(i=0;i<n;i++){
				if(suit[i]==suitlib[j]&&num[i]==k){
					exist=0;
				}
			}
			if(exist==1){
				printf("%c %d\n",suitlib[j],k);
			}
		}
	}
	return 0;
}

Measured memory_bytes: 2752
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String args[]) {

        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        Integer[] p = new Integer[n];
        for (int i = 0; i < n; i++) {
            p[i] = Integer.parseInt(sc.next());
        }

        Arrays.sort(p);
        int result = 0;
        for (int i = 0; i < n; i++) {
            if (i == p.length- 1) {
                result += p[i] / 2;
            } else {
                result += p[i];
            }
        }

        System.out.println(result);
    }
}

Measured memory_bytes: 22100
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StringReader;
import java.util.StringTokenizer;

public class Main  implements Runnable {
	public static void main(String[] args) {
		new Thread(null, new Main(), "", 32 * 1024 * 1024).start(); //
	}
	public void run() {
		FastScanner sc = new FastScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int a = Integer.parseInt(sc.next());
		int b = Integer.parseInt(sc.next());
		out.println((b-1+(a-1)-1)/(a-1));
		out.flush();
	}

    static class FastScanner {
        private BufferedReader reader = null;
        private StringTokenizer tokenizer = null;
        public FastScanner(String in) {
        	StringReader sr = new StringReader(in);
            reader = new BufferedReader(new BufferedReader(sr));
            tokenizer = null;
        }
        public FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }
        public String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
    }
}

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


using namespace std;


int main ()
{
	long long int n;
	int m;
	cin >> n >> m;
	int a[m],sum=0;
	for (int i=0;i<m;i++)
		{
			cin >> a[i];
			sum += a[i];
		}
	if (sum <= n)
	cout << (n-sum);
	else
	cout << "-1";
		return 0;
}

Measured memory_bytes: 3664
a, b, c, d = map(int, input().split())
#最大公約数
def gcd(a,b):
    while b:
        a,b = b,a%b
    return a

#最小公倍数
def lcm(a,b):
    return a*b//gcd(a,b)

c_div_a = (a-1) // c
c_div_all = b // c

d_div_a = (a-1) // d
d_div_all = b // d


cd_div_a = (a-1) // int( lcm(c, d) )
# print("cd_div_a", cd_div_a)
cd_div_all = b // int( lcm(c, d) )
# print("cd_div_all", cd_div_all)


div_a = c_div_a + d_div_a - cd_div_a
div_all = c_div_all + d_div_all - cd_div_all

print( (b - (a-1)) - (div_all - div_a) )


Measured memory_bytes: 3064
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.parents[x] > self.parents[y]:
      x, y = y, x
    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def size(self, x):
    return -self.parents[self.find(x)]

  def same(self, x, y):
    return self.find(x) == self.find(y)

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    from collections import defaultdict
    ret = defaultdict(list)
    for i in range(self.n):
      ret[self.find(i)].append(i)
    return ret

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = map(int, input().split())
uf = UnionFind(N)

for _ in range(M):
  A, B = map(lambda x:int(x)-1, input().split())
  uf.union(A, B)

print(-min(uf.parents))

Measured memory_bytes: 14820
#include <cstdio>

int N,C;
int s[100000] ,t[100000] ,c[100000];
int sm [200002];
int tt [200002];
int  main()
{
scanf ("%d%d",&N,&C);
for(int i=0;i<N;i++)
scanf ("%d%d%d",&s[i],&t[i],&c[i]);
for(int i=1;i<=C;i++)
{
for(int j=0;j <200002;j++)tt[j]=0;
for(int j=0;j<N;j++)if(c[j]==i)tt[s[j]*2-1]++ ,tt[t[j]*2]--;
for(int j=1;j <200002;j++)tt[j]+=tt[j-1];
for(int j=0;j <200002;j++)if(tt[j]>0)sm[j]++;
}
int mx=0;
for(int j=0;j <200002;j++)if(mx <sm[j])mx=sm[j];
printf ("%d\n",mx);
}

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

int main() {
	long long H;
	cin >> H;
	long long tmp = 1, ans = 0;
	for (int i = 0; i <= (int)log2(H); i++) {
		ans += tmp;
		tmp *= 2;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

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

    if(a == b){
        cout << "Draw" << endl;
    }
    else if(a == 1){
        cout << "Alice" << endl;
    }
    else if(b == 1){
        cout << "Bob" << endl;
    }
    else if(a > b){
        cout << "Alice" << endl;
    }
    else{
        cout << "Bob" << endl; 
    }
}

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

// 水平方向での切断を全部試しながら貪欲に鉛直方向に切る

// c[i][j]: 上からi個目の部分チョコレートのj列目までの領域に存在するホワイトチョコレートの個数
int c[10][1005];

const int INF = 1001001001;

int main() {
    int h, w, k; cin >> h >> w >> k;
    int ans = INF;
    vector<string> s(h);
    for (int i = 0; i < h; i++) cin >> s[i];

    // 水平方向の切断をすべて試す
    for (int div = 0; div < (1 << (h-1)); div++) {
        // 水平方向に切ったときの分割数（ex. 3回水平方向に切ったら4つ）
        int g = 0;

        // id: 上からi行目の板チョコが何番目の部分に含まれているかを記録
        vector<int> id(h);

        for (int i = 0; i < h; i++) {
            id[i] = g;
            if ((div >> i) & 1) { // divのi桁目に1が立っていればそこでチョコを分割
                g++;
            }
        }
        g++; // 植木算的に，グループ数 = 切れ込み数 + 1

        for (int i = 0; i < g; i++) {
            for (int j = 0; j < w; j++) {
                c[i][j] = 0;
            }
        }
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                c[id[i]][j] += (s[i][j] == '1') ? 1 : 0;
            }
        }

        int num = g - 1; // 板チョコを水平方向に切断してg個の部分チョコレートにしているのですでにg-1回切っている

        vector<int> now(g);

        // j列目で鉛直方向に切断したときに，各領域に含まれるホワイトチョコレートの個数がk個以下であるかを判定する関数
        auto add = [&](int j) {
            for (int i = 0; i < g; i++) now[i] += c[i][j];
            for (int i = 0; i < g; i++) if (k < now[i]) return false;
            return true;
        };

        // 貪欲に左から右へ着る場所をずらしていく
        for (int j = 0; j < w; j++) {
            if (!add(j)) {
                num++;
                now = vector<int>(g);
                if (!add(j)) {
                    num = INF;
                    break;
                }
            }
        }
        ans = min(ans, num);
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
  string S1 = "Sunny";
  string S2 = "Cloudy";
  string S3 = "Rainy";
  string S ;
    
  cin >> S ;
  
  if (S == S1){
    cout << S2 << endl;
  }
  else if (S == S2){
    cout << S3 << endl;
  }
  else{
    cout << S1 << endl;
  }
}
  
  

Measured memory_bytes: 256
#import<map>
long h,w,a,b,c,d,D[10]={0,2,2,1,2,0,1,1},t[10],i;std::map<long,int>m;main(){for(*t=(scanf("%d%d%*d",&h,&w)-h)*(2-w);~scanf("%d%d",&a,&b);i=0)for(;i<9;)if((c=a+D[i])>2&(d=b+D[++i])>2&c<=h&d<=w)t[c=m[c*w+d]++]--,t[c+1]++;for(;i<10;)printf("%ld ",t[i++]);}

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

int main() {

  int n, x;
  int l[101];
  int d = 0;  //現在の座標D
  int cnt = 0;

  cin >> n >> x;

  for(int i=0; i<n; ++i) cin >> l[i];

  for(int i=0; i<n; ++i) {

    if(d<=x) ++cnt;

    d = d + l[i];
  }

  if(d<=x) ++cnt;

  cout << cnt << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stdio.h>
#include <cmath>
#include <cctype>
#include <map>
#include <set>

const int INT_INF = 1e9;
const long long LONG_INF = 1e18;
const long long MOD = 1e9 + 7;
const double PI = 3.14159265358979323846;

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1), c(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i];
    }
    for (int i = 1; i <= n - 1; i++)
    {
        cin >> c[i];
    }

    int ans = 0;
    ans += b[a[1]];
    for (int i = 2; i < n + 1; i++)
    {
        ans += b[a[i]];
        if (a[i] == a[i - 1] + 1)
        {
            ans += c[a[i - 1]];
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3632
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
int n,m,a[500050],k,b[500050],ans,ok[2];
int check(int x)
{
	ok[0]=ok[1]=1000000;
	for(int i=1;i<=k;i++)
	b[i]=(a[i]>=x);
	b[0]=b[k+1]=10;
	for(int i=1;i<=k;i++)
	{
		if(b[i]==b[i-1]||b[i]==b[i+1])
		{
			ok[b[i]]=min(ok[b[i]],abs(i-n));
		}
	}
	//cout<<x<<" "<<ok[0]<<" "<<ok[1]<<endl;
	if(ok[1]==ok[0]) return b[1];
	return ok[1]<ok[0];
}
int main()
{
	cin>>n;
	k=2*n-1;
	for(int i=1;i<=k;i++)
	{
		scanf("%d",&a[i]);
	}
	int l=1,r=k;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(check(mid)) ans=mid,l=mid+1;
		else r=mid-1;
	}
	cout<<ans;
}

Measured memory_bytes: 1920
import java.util.Scanner;

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

		int amt = S.length();
		String T_part = T.substring(0, amt);

		if(T_part.equals(S) && T.length() == (amt + 1)){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}

		scan.close();
	}
}

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

int main(){
    int a , b , c , k;
    cin >> a >> b >> c >> k;
    if(k <= a)cout << k << endl;
    else if (k <= a + b)cout << a << endl;
    else cout << a - (k - a - b) << endl;
}
    


Measured memory_bytes: 3636
# maximum sum of minimum
n=int(input())
node={i:[]for i in range(n+1)}
visited=[False for i in range(n+1)]

#尋ねたことがあるかどうか確認するためのリスト
first=0

for _ in range(n-1):
    a,b=map(int,input().split())
    node[a].append(b)
    node[b].append(a)
    if _==0:
        first+=a
        

dictionary=[0 for i in range(n+1)]
#答を格納するためのリスト
clist=list(map(int,input().split()))
clist=sorted(clist,reverse=True)
counter=0
dictionary[first]=clist[0]
K=sum(clist[1:])
from collections import deque
d=deque()
e=deque()
d.append(first)
visited[first]=True
while d:
    for some in d:
        for point in node[some]:
            if visited[point]==False:
                #まだ訪れたことのない頂点にあった場合
                counter+=1
                visited[point]=True
                dictionary[point]=clist[counter]
                e.append(point)
            else:
                pass
    d=e
    e=deque()
print(K)
print(*dictionary[1:])


Measured memory_bytes: 51672
num = gets.chomp.split.map!(&:to_i)
mens = []
(1..num[0]).each{ |i|
  mens.push(i)
}
(1..num[1]).each{ |j|
  out = gets
  sakujo = gets.chomp.split.map!(&:to_i)
  mens -= sakujo
}
puts mens.count

Measured memory_bytes: 14288
// failed to generate code

#include <algorithm>
#include <bitset>
#include <cassert>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stdio.h>
#include <string>
#include <vector>

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define POW(n) ((n) * (n))
#define ALL(a) (a).begin(), (a).end()

using namespace std;

namespace Dump {
#define dump(...) Dump::print(#__VA_ARGS__, __VA_ARGS__)
static std::vector<string> dumpKey;
static string dumpKeyBuf;

void print() { cerr << endl; }
template <class Head, class... Tail> void print(Head &&head, Tail &&... tail) {
  if (dumpKey.empty()) {
    dumpKeyBuf = head;
    dumpKeyBuf.erase(std::remove_if(dumpKeyBuf.begin(), dumpKeyBuf.end(),
                                    [](char c) { return c == ' '; }),
                     dumpKeyBuf.end());

    std::istringstream stream(dumpKeyBuf);
    string field;
    while (std::getline(stream, field, ','))
      dumpKey.push_back(field);

    reverse(dumpKey.begin(), dumpKey.end());
  } else {
    cerr << dumpKey.back() << ":" << head << "  ";
    dumpKey.pop_back();
  }
  Dump::print(std::move(tail)...);
}
}

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<unsigned long long> vull;
typedef pair<int, int> pii; // p.first p.second

// ll n = to_T<ll>("114514")
template <class T> T to_T(const string &s) {
  istringstream is(s);
  T res;
  is >> res;
  return res;
}
template <class T> string to_s(const T &a) {
  ostringstream os;
  os << a;
  return os.str();
}

int binarySearch(long double key) {
  if (key == 0)
    return -1;
  int left = 0;
  int right = 3501;

  //残り10以下になるまで探索
  while (right - left > 10) {
    int mid = (left + right) / 2;
    long double buf = 1.d / mid;

    if (buf == key)
      return mid;

    if (buf > key) {
      left = mid;
    } else {
      right = mid;
    }

    // cerr << left << " " << right << endl;
  }

  //あとは愚直に
  for (int i = left; i <= right; ++i) {
    long double buf = 1.d / i;

    if (buf == key) {
      return i;
    }
  }

  return -1;
}

ll N;

void think() {
  cin >> N;

  long double ans = 4.d / (long double)N;

  // if (false) {
  FOR(h, 1, 3501) {
    FOR(n, 1, 3501) {
      long double buf = ans - 1.d / (long double)h - 1.d / (long double)n;
      if (buf <= 0)
        continue;

      int w = (int)(1.d / buf);

      // dump(binarySearch(buf));
      // dump(ans, buf);
      // int w = binarySearch(buf);
      if (w <= 0)
        continue;

      if (ans !=
          (1 / (long double)h + 1.d / (long double)n + 1.d / (long double)w))
        continue;

      dump(ans, (1.d / h + 1.d / n + 1.d / w));
      cout << h << " " << n << " " << w << endl;
      return;
    }
  }
  // }
}

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


Measured memory_bytes: 256
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
mx = A[:M]
t = False

for n in mx:
    if n/sum(A) < (1/(4*M)):
        print("No")
        t = True
        break

if not t:
    print("Yes")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double lf;
typedef pair<ll,ll> ii;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define RST(i,n) memset(i,n,sizeof i)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(),a.end()
#define X first
#define Y second
#define mkp make_pair
#define pb push_back
#define eb emplace_back
#define pob pop_back
#ifdef cold66
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<", ";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#endif // cold66
//}
template<class T> inline bool chkmax(T &a, const T &b) { return b > a ? a = b, true : false; }
template<class T> inline bool chkmin(T &a, const T &b) { return b < a ? a = b, true : false; }
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;

const ll MAXn=1e5+5,MAXlg=__lg(MAXn)+2;
const ll MOD=1000000007;
const ll INF=0x3f3f3f3f;

ll n;
string s;
bool ani[MAXn];
bool ok;
bool gogo(){
  bool tg;
  if (ani[0]) {
    if (s[0] == 'o') tg = ani[1];
    else tg = !ani[1];
  }
  else {
    if (s[0] == 'o') tg = !ani[1];
    else tg = ani[1];
  }
  debug(tg);
  for (int i=1;i<n-1;i++) {
    if (ani[i]) {
      if (s[i] == 'o') ani[(i+1)%n] = ani[i-1];
      else ani[(i+1)%n] = !ani[i-1];
    }
    else {
      if (s[i] == 'o') ani[(i+1)%n] = !ani[i-1];
      else ani[(i+1)%n] = ani[i-1];
    }
  }
  debug(ani[n-1],tg);
  if (ani[n-1] != tg) return false;
  if (ani[n-1]) {
    if (s[n-1] == 'o' && (ani[n-2] ^ ani[0])) return false;
    else if (s[n-1] == 'x' && !(ani[n-2] ^ ani[0])) return false;
  }
  else {
    if (s[n-1] == 'x' && (ani[n-2] ^ ani[0])) return false;
    else if (s[n-1] == 'o' && !(ani[n-2] ^ ani[0])) return false;
  }
  return true;
}
int main(){
  IOS();
  cin >> n;
  cin >> s;

  REP (i,4) {
    REP (j,2) {
      if ((1<<j)&i) ani[j] = true;
      else ani[j] = false;
    }
    pary(ani,ani+2);
    debug(i);
    ok = gogo();
    if (ok) break;
  }
  if (ok) {
    REP (i,n) cout << (ani[i] ?'S':'W');
  }
  else cout << -1;
  cout << endl;
}


Measured memory_bytes: 720
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
#define show(obj) for(auto x:obj)cout<<x<<' ';cout<<endl;
#define line "----------"
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
	int N,A,B;
	cin>>N>>A>>B;
	int nax = A+B;
	int cnt_b = 0;
	string s;cin>>s;
	rep(i,N){
		if(nax==0){cout<<"No"<<endl; continue;}
		char c = s[i];
		if(c == 'b')cnt_b++;
		if(c == 'a'){
			cout<<"Yes"<<endl; --nax;
			continue;
		}
		if(c == 'b' && cnt_b<=B){
			cout<<"Yes"<<endl; --nax;
			continue;
		}
		cout<<"No"<<endl;
	}
	return 0;
}

Measured memory_bytes: 896
INF = 10**9 + 7


def main():
    N, K = (int(i) for i in input().split())
    H = [int(i) for i in input().split()]
    dp = [INF]*N
    dp[0] = 0
    for i in range(N):
        for k in range(1, K+1):
            if i + k >= N:
                break
            dp[i+k] = min(dp[i+k], dp[i] + abs(H[i+k] - H[i]))
    print(dp[-1])


if __name__ == '__main__':
    main()


Measured memory_bytes: 84760
#include<stdio.h>

int main()
{
    int num,i,N;
    int sum=0,result=0;

    scanf("%d",&N);

    for(i=0;i<N;i++)
    {
        scanf("%d",&num);
        sum+=num;
    }
    result=sum-N;
    printf("%d\n",result);


    return 0;
}


Measured memory_bytes: 1736
/* {{{ Definitions */
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <ios>
#include <utility>
#include <queue>
#ifdef _WIN32
#include "debug.hpp"
#endif
using namespace std;

#define rep(i, N)  for(int i = 0; i < (N); i++)
#define reps(i, N) for(int i = 1; i <= (N); i++)
#define repr(i, N) for(int i = (N) - 1; i >= 0; i--)
#define pub push_back

template<typename T> 
void chmax(T &a, T b){ a = max(a, b); };
template<typename T> 
void chmin(T &a, T b){ a = min(a, b); };

typedef long long ll;
typedef pair<int, int> P;
const int INF = 100000000;
const ll LINF = 10000000000000000;
const int MOD = 1000000007;
/* }}}------------------------------------------- */
int N, M, a[1000];
int c[1000];

ll dp[1001][1 << 12 + 1];
void solve(){
	rep(i, M + 1)
		rep(j, 1 << N)
			dp[i][j] = LINF;
	dp[0][0] = 0;
	rep(i, M){
		rep(j, 1 << N){
			if(dp[i][j] != LINF){
				chmin(dp[i + 1][j | c[i]], dp[i][j] + a[i]);
				chmin(dp[i + 1][j], dp[i][j]);
			}
		}
	}
	if(dp[M][(1 << N) - 1] != LINF)
		cout << dp[M][(1 << N) - 1] << endl;
	else
		cout << -1 << endl;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> N >> M;
	rep(i, M) {
		cin >> a[i];
		int b;
		cin >> b;
		rep(j, b){
			int C;
			cin >> C;
			c[i] |= 1 << (C - 1);
		}
	}
		solve();
	return 0;
}


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

using namespace std;
typedef long long int LL;
typedef long long int ll;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SP << " " <<

LL mod = 1000000007;

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

  LL N, D;
  cin >> N >> D;
  cout << (N - 1) / (2 * D + 1) + 1 << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

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

int main(){
    int k;
    cin >> k;
    long long count = 0;
    for (int a = 1; a <= k; a++) {
        for (int b = 1; b <= k; b++) {
            for (int c = 1; c <= k; c++) {
                int g;
                g = gcd(a, b);
                g = gcd(g, c);
                count += g;
            }
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 3636
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

x, y, z, k = map(int, readline().split())
a = list(map(int, readline().split()))
b = list(map(int, readline().split()))
c = list(map(int, read().split()))
ab = [0] * x * y
for i, aa in enumerate(a):
    for j, bb in enumerate(b):
        ab[i * y + j] = aa + bb
ab = sorted(ab, reverse=True)[:k]
c = sorted(c, reverse=True)
ans = [0] * k * z
for i, abab in enumerate(ab):
    for j, cc in enumerate(c):
        ans[i * z + j] = abab + cc
ans.sort(reverse=True)
print('\n'.join(map(str, ans[:k])))


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

int main() {
  int A, B;
  cin >> A >> B;

  int count=0;
  int d[5];
  for(int i=A; i<=B; i++) {
    int num=i;
    for(int j=4; j>=0; j--) d[j]=num%10, num/=10;
    if(d[0]==d[4]&&d[1]==d[3]) count++;
  }
  cout << count << endl;
}


Measured memory_bytes: 256
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,k = readInts()
H = sorted(readInts(),reverse=True)
if n <= k:
    print(0)
else:
    print(sum(H[k:]))


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

int main()
{   
    string s;
    cin>>s;
    
    
    for(int i=0;i<s.size();i++){
        if(s[i]=='1'){
            s[i]='9';
        }
        else if(s[i]=='9') s[i]='1';
    }

    cout<<s<<endl;
    
}

Measured memory_bytes: 256
#! env python
# -*- coding: utf-8 -*-

import os
import sys


# ac_py.main
# Date: 2020/06/08
# Filename: main 
# Author: acto_mini

def main():
    A = int(input())
    B = int(input())
    C = int(input())
    X = int(input())

    result = 0

    for i in range(A + 1):
        for j in range(B + 1):
            for k in range(C + 1):
                if (500 * i + 100 * j + 50 * k) == X:
                    result += 1
    print(result)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 38896
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>

using namespace std;

typedef long long ll;
// constexpr ll MOD = 998244353;
constexpr ll MOD = 1000000007;

// struct UnionFind {
//     vector<ll> par;
//     vector<ll> siz;
    
//     UnionFind(ll N): par(N), siz(N,1) {
//         for (ll i=0;i<N;i++) par[i] = i;
//     }

//     ll root(ll x) {
//         if (par[x] == x) return x;
//         else return par[x] = root(par[x]);
//     }

//     void unite(ll x, ll y) {
//         ll rx = root(x);
//         ll ry = root(y);
//         if (rx == ry) return;
//         // if (siz[rx] < siz[ry]) swap(rx,ry);
//         par[rx] = ry;
//         siz[ry] += siz[rx];
//     }

//     bool same(ll x, ll y) {
//         ll rx = root(x);
//         ll ry = root(y);
//         return rx == ry;
//     }

//     ll size(ll x) {
//         return siz[root(x)];
//     }
// };

//     vector<ll> par;
//     vector<ll> siz;
    
//     UnionFind(ll N): par(N), siz(N,1LL) {
//         for (ll i=0;i<N;i++) par[i] = i;
//     }

//     ll root(ll x) {
//         if (par[x] == x) return x;
//         else return par[x] = root(par[x]);
//     }

//     void unite(ll x, ll y) {
//         ll rx = root(x);
//         ll ry = root(y);
//         if (rx == ry) return;
//         par[rx] = ry;
//         siz[ry] += siz[rx];
//     }

//     bool same(ll x, ll y) {
//         ll rx = root(x);
//         ll ry = root(y);
//         return rx == ry;
//     }

//     ll size(ll x) {
//         return siz[root(x)];
//     }
// };

int main(void) {
    ll X;
    cin >> X;
    ll y = 100;
    int k = 0;
    while (y < X) {
        y = (ll)floor(y*1.01);
        k++;
    }
    cout << k << endl;

    return 0;
}


Measured memory_bytes: 3744
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353LL;
clock_t TIME_START, TIME_END;
void program_end()
{
#ifdef ONLINE
    printf("\nTime used: %.6lf(s)\n", ((double)TIME_END - TIME_START) / CLOCKS_PER_SEC);
    system("pause");
#endif
}
int n;
char s[N];
ll dp[2][3000];

void solve()
{
    // cin >> n;
    ll ans = 0;
    scanf("%s", s + 1);
    n = strlen(s + 1);
    int f = 1;
    for (int i = 1; i <= n; ++i)
    {
        memarray(dp[f], 0);
        dp[f][s[i] - '0']++;
        for (int j = 0; j < 2019; ++j)
        {
            dp[f][(j * 10 + s[i] - '0') % 2019] += dp[f ^ 1][j];
        }
        ans += dp[f][0];
        f ^= 1;
    }
    cout << ans << endl;
}

int main()
{
    TIME_START = clock();
    int Test = 1;
    // cin >> Test;
    while (Test--)
        solve();
    TIME_END = clock();
    program_end();
    return 0;
}

Measured memory_bytes: 3896
#include <bits/stdc++.h>
#define INF pow(10, 9) + 7
#define rep(i, N) for(ll i = 0; i < N; i++)
#define rep2(i, j, k) for(ll i = j; i < k; i++)
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define chmax(x, y) x = max(x, y)
#define print(x) cout << x << "\n"
#define ALL(v) v.begin(), v.end()
#define SUM(v) accumulate(ALL(v), 0)
#define MAX(v) *max_element(ALL(v))
#define MIN(v) *min_element(ALL(v))
#define SORT(v) sort(ALL(v))
#define REV(v) reverse(ALL(v))
typedef long long ll;
using namespace std;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vs = vector<string>;
using vvs = vector<vector<string>>;

void solve(){
	
	ll N, K, cnt, num;
	cin >> N >> K;
	string S;
	cin >> S;
	
	vl v(0);
	ll num0 = 0;
	ll ans = 0;
	ll ind = 0;
	
	if(S[0] == '1'){
		
		while(ind < N){
			
			cnt = 0;
		
			while(ind < N && S[ind] == '1'){
				cnt += 1;
				ind += 1;
			}
			v.push_back(cnt);
			
			cnt = 0;
			
			while(ind < N && S[ind] == '0'){
				cnt += 1;
				ind += 1;
			}
			v.push_back(cnt);
			num0 += 1;
		
		}
		
		cnt = 0;
		num = v.size();
		
		if(num0 <= K) ans = N;
		
		else{
			
			rep(i, 2 * K + 1) cnt += v[i];
			
			rep(i, num0 - K + 1){
				
				chmax(ans, cnt);
				cnt -= v[2 * i];
				cnt -= v[2 * i + 1];
				cnt += v[2 * i + 2 * K + 1];
				if(2 * i + 2 * K + 1 + 1 < num)  cnt += v[2 * i + 2 * K + 1 + 1];
			
			}
			
		}

	}
	
	else{
		
		ind = 0;
		
		while(ind < N){
			
			cnt = 0;
		
			while(ind < N && S[ind] == '0'){
				cnt += 1;
				ind += 1;
			}
			v.push_back(cnt);
			
			cnt = 0;
			
			while(ind < N && S[ind] == '1'){
				cnt += 1;
				ind += 1;
			}
			v.push_back(cnt);
			num0 += 1;
		
		}
		
		cnt = 0;
		num = v.size();
		
		if(num0 <= K) ans = N;
		
		else{
			
			rep(i, 2 * K) cnt += v[i];
			
			rep(i, num0 - K + 1){
				
				chmax(ans, cnt);
				if(i == 0)  cnt -= v[0];
				else{
					cnt -= v[2 * i - 1];
					cnt -= v[2 * i];
				}
				cnt += v[2 * i + 2 * K];
				if(2 * i + 2 * K + 1 < num)  cnt += v[2 * i + 2 * K + 1];
			
			}
			
		}

	}
	
	print(ans);

}	

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


Measured memory_bytes: 4472
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
int main()
{
    int a[50][50],b[50],c[50][50]={0},d[50]={0};
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        cin>>a[i][j];
    }
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>b[i];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<3;j++)
        {
            for(int k=0;k<3;k++)
            {
                if(b[i]==a[j][k])
                {
                    c[j][k]=1;
                }
            }
        }
    }
    int sum1=0,sum2=0,sum3=0,sum4=0;
    for(int i=0;i<3;i++)
    {
        sum1=0;
        for(int j=0;j<3;j++)
        {
            if(c[i][j]==1)
            {
                sum1++;
            }
            if(sum1==3)
            break;
        }
        if(sum1==3)
        break;
    }
    for(int i=0;i<3;i++)
    {
        sum2=0;
        for(int j=0;j<3;j++)
        {
            if(c[j][i]==1)
            {
                sum2++;
            }
            if(sum2==3)
            break;
        }
        if(sum2==3)
        break;
    }
    for(int i=0;i<3;i++)
    {
        if(c[i][i]==1)
        {
            sum3++;
        }
    }
    for(int i=0;i<3;i++)
    {
        if(c[i][2-i]==1)
        {
            sum4++;
        }
    }
    if(sum1==3||sum2==3||sum3==3||sum4==3)
    {
        cout<<"Yes";
    }
    else 
    {
        cout<<"No";
    }
    return 0;
}

Measured memory_bytes: 256
H, W, K = map(int, input().split())
lis =[]
for i in range(H):
    a =[]
    k = input()
    for j in range(W):
        if k[j]==".":
            lis.append(0)
        else:
            lis.append(1)
ans = 0
from itertools import product
import copy
one = list(product([False,True],repeat=H))
two = list(product([False,True],repeat=W))
for i in one:
    for j in two:
        target = copy.copy(lis)
        t = 0
        s = 0
        for k in i:

            if k == True:
                for l in range(W):
                    target[t+l] =0
            t += W
        for m in j:

            if m == True:
                for n in range(H):
                    target[s + n*W]=0
            s += 1
        if target.count(1) == K:
            ans+=1

print(ans)

Measured memory_bytes: 9356
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 4000000000000000000LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)


int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  std::cout << std::fixed << std::setprecision(6);
  std::cerr << std::fixed << std::setprecision(6);

  long long r, D, x;

  std::cin >> r >> D >> x;

  for (int i = 0; i < 10; i ++)
    std::cout << (x = r * x - D) << std::endl;

  return 0;
}


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

#define fastIO ios::sync_with_stdio(false);cout.tie(0);cin.tie(0);
#define endl '\n'
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define MP make_pair
#define inf INT_MAX
#define minf INT_MIN

typedef long long int lli;

ofstream outfile;
ifstream infile;

int main()
{
	infile.open("input.txt");
	outfile.open("output.txt");

	lli n, m;
	cin >> n >> m;

	if( n >= m/2)
		cout << m/2 << "\n";
	else
	{
		m -= 2*n;
		cout << n+m/4 << "\n";
	}
}

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

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

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

int main(){
	int h, w;
	cin >> h >> w;
	int a, b;
	cin >> a >> b;
	if(a*b==0){
		if(a==0){
			rep(i, b){
				rep(j, w)cout << 1;
				cout << endl;
			}
			rep(i, h-b){
				rep(j, w)cout << 0;
				cout << endl;
			}
			return 0;
		}
		rep(i, h){
			rep(j, a)cout << 1;
			rep(j, w-a)cout << 0;
			cout << endl;
		}
		return 0;
	}

	rep(i, h){
		rep(j, w){
			if((b>i)!=(a>j))cout << 1;
			else cout << 0;
		}
		cout << endl;
	}




	return 0;
}


Measured memory_bytes: 1280
from itertools import product
def f(A, B, k):
    S = [a+b for a, b in product(A, B)]
    S.sort(reverse = True)
    return S[:k]
x, y, z, k = map(int, input().split())
*A, = map(int, input().split())
*B, = map(int, input().split())
*C, = map(int, input().split())
S = f(f(A, B, k), C, k)
for s in S: print(s)

Measured memory_bytes: 142288