akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>  
using namespace std;
using ll = long long int;
using pii = pair<int, int>;
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0; i<(int)(n); i++)

int main() {
  int n;cin>>n;
  vector<int> v(n);

  rep(i,n){
    cin>>v.at(i);
    v.at(i)/=400;
  }
    
  set<int> s;
  int c=0;
  rep(i,n){
    if(v.at(i)>=8){c++;}
    else{s.insert(v.at(i));}
  }
  int count=s.size();

  cout<<max(1,count)<<" "<<count+c;
}
      



Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace Get_AC
{
    class Program
    {
        public static void Main(string[] args)
        {
            using (var sc = new SetConsole())
            {
                var s = Console.ReadLine();
                var t = Console.ReadLine();
                var dic = new Dictionary<char, char>();
                string result = "Yes";
                for (int i = 0; i < s.Length; i++)
                {
                    if (dic.ContainsKey(s[i]))
                    {
                        if (dic[s[i]] != t[i])
                        {
                            result = "No";
                            break; 
                        }
                    }
                    else
                    {
                        dic.Add(s[i], t[i]);
                    }
                }
                dic.Clear();
                for (int i = 0; i < s.Length; i++)
                {
                    if (dic.ContainsKey(t[i]))
                    {
                        if (dic[t[i]] != s[i])
                        {
                            result = "No";
                            break;
                        }
                    }
                    else
                    {
                        dic.Add(t[i], s[i]);
                    }
                }

                CWrite(result);
            }
        }

        static string[] GetArrayCharInput() => Console.ReadLine().Split();
        static int[] GetArrayIntInput() => Console.ReadLine().StringToIntArray();
        static int GetIntInput() => Console.ReadLine().ToInt();
        static void CWrite(string str) => Console.WriteLine(str);

    }

    class SetConsole : IDisposable
    {
        StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
        public SetConsole()
        {
            sw.AutoFlush = false;
            Console.SetOut(sw);
        }
        public void Dispose()
        {
            Console.Out.Flush();
            sw.AutoFlush = true;
            Console.SetOut(sw);
        }
    }

    static class ExtentionsLibrary
    {
        public static int[] StringToIntArray(this string str) =>
            str.Split().Select(int.Parse).ToArray();
        public static int ToInt(this string str) => int.Parse(str);
    }
}


Measured memory_bytes: 14688
#include <bits/stdc++.h>
#define pi 3.14159
using namespace std;

int main()
 {
 	int h,a,m;
 	cin>>h>>a;
 	if(h%a==0)
 		m=h/a;
	else
		m=h/a+1;
	cout<<m<<endl;	
 	return 0;
}
 	
 					

Measured memory_bytes: 3544
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)

int N, C;
int S[31][100010];

int main()
{
	scanf("%d%d", &N, &C);
	rep(i, N)
	{
		int s, t, c;
		scanf("%d%d%d", &s, &t, &c);

		S[c-1][s] += 1;
		S[c-1][t+1] += -1;
	}
	
	rep( c, C ) rep(i, 100010)
		S[c][i + 1] += S[c][i];

	int ans = 0;
	repi(i, 1, 100010)
	{
		int cnt = 0;

		rep(c, C) if( S[c][i] > 0 )
			++cnt;

		ans = std::max(ans, cnt);
	}
		

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

	return 0;
}

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

int main()
{
    long long H;
    cin >> H;

    int count = 0;
    long long ans = 0;
    while (H > 0) {
        H /= 2;
        ans += pow(2, count);
        count++;
    }
    cout << ans << endl;
    return 0;
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define each(it,v) for(auto &it : v)
#define mod 1000000007
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define vl vector<long>
#define P pair<int,int>
using namespace std;

main()
{
        string s,t; cin>>s>>t;
        int ans=0;
        rep(i,3)ans+=s[i]==t[i];
        cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<stdio.h>
 
int main(int argc, char* argv[])
{
  int a, b;
  char op;
  scanf("%d %c %d", &a, &op, &b);
  while(op != '?'){
    switch(op){
      case '+':
        printf("%d\n", a+b);
        break;
      case '-':
        printf("%d\n", a-b);
        break;
     case '/':
        printf("%d\n", a/b);
        break;
     case '*':
        printf("%d\n", a*b);
        break;
    }
    scanf("%d %c %d", &a, &op, &b);  
  }
  return(0);
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,k;
	scanf("%d",&n);
	vector<vector<int>>g(n);
	for(int i=0;i<n-1;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		a--;
		b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	vector<int>d(n,-1);
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
	scanf("%d",&k);
	for(int i=0;i<k;i++)
	{
		int v,p;
		scanf("%d%d",&v,&p);
		v--;
		d[v]=p;
		pq.push(pair<int,int>(p,v));
	}
	while(!pq.empty())
	{
		pair<int,int>p=pq.top();
		pq.pop();
		int u=p.second;
		for(int v:g[u])
		{
			if(d[v]==-1)
			{
				d[v]=d[u]+1;
				pq.push(pair<int,int>(d[v],v));
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j:g[i])
		{
			if(abs(d[i]-d[j])!=1)
			{
				puts("No");
				return 0;
			}
		}
	}
	puts("Yes");
	for(int i=0;i<n;i++)
		printf("%d\n",d[i]);
	return 0;
}


Measured memory_bytes: 7924
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
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; }
typedef long long ll;
typedef pair<int,int> P;

bool check(ll n){
    vector<int> m(10,0);
    while(n>0){
        m[n%10]++;
        n/=10;
    }
    if(m[3]&&m[5]&&m[7])return 1;
    else return 0;
}

int ans;
ll N;

void dfs(ll now){
    if(now>N)return;
    if(check(now))ans++;
    ll next = now*10;
    dfs(next+3);
    dfs(next+5);
    dfs(next+7);
    return;
}

int main(){
    cin >> N;
    dfs(0);
    cout << ans << endl;
}

Measured memory_bytes: 256
n,a,b=map(int,input().split())
cnt=0
for i in range(n+1):
  n_list=list(str(i))
  n_listy=[int(s) for s in n_list]
  if sum(n_listy)>=a and sum(n_listy)<=b:
    cnt+=i
    
print(cnt)
    
   



Measured memory_bytes: 9080
#include <algorithm>
#include <climits>
#include <cmath>
#include <csignal>
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>

using Graph = std::vector<std::vector<int>>;
using WGraph = std::vector<std::vector<std::pair<int, long long>>>;
using ll = long long;
using namespace std;

int main() {
    int n = 0, m = 0, q = 0;
    cin >> n >> m >> q;
    vector<vector<int>> cnt(n+1, vector<int>(500));
    int l = 0, r = 0;
    for (int i=0; i<m; i++) {
        cin >> l >> r;
        int tmp = r - l;
        cnt.at(l).at(tmp)++;
    }
    for (int i=0; i<n+1; i++) {
        for (int j=1; j<500; j++) {
            cnt.at(i).at(j) += cnt.at(i).at(j-1);
        }
    }
    vector<int> ans(q);
    for (int i=0; i<q; i++) {
        cin >> l >> r;
        int tmp = 0;
        for (int j=l; j<=r; j++) {
            tmp += cnt.at(j).at(r-j);
        }
        ans.at(i) = tmp;
    }
    for (int x : ans) {
        cout << x << endl;
    }
    return 0;
}


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

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  int L = A + B;
  int R = C + D;
  if (L > R) {
    cout << "Left" << endl;
  }
  else if (L == R) {
    cout << "Balanced" << endl;
  }
  else {
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 256
//Five Transportations

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define irep(i,a) for(auto i = a.begin(); i != a.end(); ++i)
#define nvarep(n,a) ll n;cin>>n;vector<ll>a(n);rep(i,0,n)cin>>a[i]
#define vecrep(n,a,type) vector<type>a(n);rep(i,0,n)cin>>a[i]
#define lcm(a,b) (a/__gcd(a, b)*b)
#define range(a) (a).begin(),(a).end() 
#define pb push_back
#define mp make_pair
#define nnn "\n"
#define spa " "

using p = pair<ll,string>;
using garph = vector<vector<ll>>;
const int inf = 2147483647;//2*10^9
const ll INF = 9223372036854775807;//9*10^18

signed main (){
    double n;cin>>n;
    vector<double>a(5);
    rep(i,0,5)cin>>a[i];
    double c = *min_element(range(a));
    cout<<(ll)(ceil(n/c)+4)<<nnn;
    return 0;
}

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

int main()
{
    int N,A,B;
    cin>> N >> A >> B;
    int k = B - A;
    if(k % 2){
        cout << "Borys" << endl;
    }
    else{
        cout << "Alice" << endl;
    }


    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 10000000


int main(){
	
	int N,M;
	cin>>N>>M;
	
	vector<vector<int>> E(N,vector<int>());
	
	for(int i=0;i<M;i++){
		int a,b;
		cin>>a>>b;
		a--;b--;
		
		E[a].push_back(b);
		E[b].push_back(a);
	}
	
	vector<bool> checked(N,false);
	
	deque<int> ans;
	ans.push_back(0);
	ans.push_back(E[0][0]);
	
	checked[0]=true;
	checked[E[0][0]]=true;
	
	while(true){
		int from = ans[0];
		int to = ans[ans.size()-1];
		
		bool f = true;
		for(int i=0;i<E[from].size();i++){
			if(checked[E[from][i]]==false){
				ans.push_front(E[from][i]);
				checked[E[from][i]]=true;
				f=false;
				break;
			}
		}
		
		for(int i=0;i<E[to].size();i++){
			if(checked[E[to][i]]==false){
				ans.push_back(E[to][i]);
				checked[E[to][i]]=true;
				f=false;
				break;
			}
		}
		
		if(f)break;
	}
	
	cout<<ans.size()<<endl;
	
	for(int i=0;i<ans.size();i++){
		if(i!=0)cout<<' ';
		cout<<ans[i]+1;
	}
	
	return 0;
}



Measured memory_bytes: 6656
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String S = sc.next();
        
        for(int i=0; i<S.length(); i++){
            int tmp = S.charAt(i)+N;
            if(tmp > 90){
                tmp = S.charAt(i) - 26 + N ;
            }
            
            System.out.print((char)tmp);
        }
   }
}


Measured memory_bytes: 38812
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int a,b,s=0;
int main()
{
	cin>>a>>b;
	for(int i=a;i<=b;i++)
	s++;
	if(a<=0&&b>=0)
	cout<<"Zero";
	else if(s%2==0||(a>0&&b>0))
	cout<<"Positive";
	else
	cout<<"Negative";
	cout<<endl;
	return 0;
} 

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

int mod(ll l,ll r){
    int minv = 200000;
    for(ll i=l;i<=r;i++){
        for(ll j=i+1;j<=r;j++){
            //cout << l << " " << r << endl;
            int imod = i % 2019;
            int jmod = j % 2019;
            int p = imod * jmod;
            int mod = p % 2019;
            //printf("%d %d %d\n",imod,jmod,p);
            if(minv > mod){
                minv = mod;
            }
        }
    }
    return minv;
}

int main(){
    ll l,r;
    cin >> l >> r;
    if(l / 2019 != r / 2019){
        cout << 0 << endl;
    }else{
        ll b = mod(l,r);
        cout << b << endl; 
    }
}

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

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

int main() {
  int n , p;
  cin >> n >> p ;
  int a[n];
  rep(i,n) cin>>a[i];
  
  int sum1=0;
  rep(i,n){
    if(a[i]%2==1) sum1++;
  }
  ll ans=pow(2,n);
  if(sum1==0 && p==0) cout<<ans;
  if(sum1==0 && p==1) cout<<0;
  if(sum1!=0) cout<<ans/2;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
vector<int>node[200005];
int counter[200005]={0};

void dfs(int pos,int from);
int main(){
  int n,q;
  cin>>n>>q;
  for(int i=0;i<n-1;i++){
    int a,b;
    cin>>a>>b;
    a--;b--;
    node[a].push_back(b);
    node[b].push_back(a);
  }
  
  for(int i=0;i<q;i++){
    int index,data;
    cin>>index>>data;
    index--;
    counter[index]+=data;
  }

  dfs(0,0);
  for(int i=0;i<n-1;i++){
    cout<<counter[i]<<' ';
  }
  cout<<counter[n-1]<<endl;
  return(0);
}

void dfs(int pos,int from){
  for(int i=0;i<node[pos].size();i++){
    int next=node[pos][i];
    if(next!=from){
      counter[next]+=counter[pos];
      dfs(next,pos);
    }
  }
  return;
}

Measured memory_bytes: 26624
module Main where

import           Control.Monad
import           Data.Maybe
import qualified Data.ByteString.Char8         as BS
import qualified Data.Vector                   as V
import qualified Data.Vector.Mutable           as VM
import qualified Data.Vector.Unboxed           as VU
import qualified Data.Vector.Unboxed.Mutable   as VUM

main :: IO ()
main = do
    n <- fst <$> (BS.getContents >>= justifyForce . BS.readInt)
    putStrLn $ show $ (n + 1) `div` 2

justifyForce :: Maybe a -> IO a
justifyForce (Just x) = pure x
justifyForce Nothing = fail "poyo"

split :: BS.ByteString -> [BS.ByteString]
split = filter (\s -> BS.length s > 0) . BS.splitWith isDelim

isDelim :: Char -> Bool
isDelim c = c == ' ' || c == '\n'


Measured memory_bytes: 380
n = int(input())
a = list(map(int, input().split()))

count = 0
for i in range(n):
    for j in range(n-1,0,-1):
        if a[j]<a[j-1]:
            key = a[j]
            a[j] = a[j-1]
            a[j-1] = key
            count += 1

string = ''
for s_val in a[:-1]:
    string += str(s_val) + ' '
string += str(a[-1])
print(string)
print(count)


Measured memory_bytes: 5592
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <complex>
#include <ctime>
#include <cstdlib>

using namespace std;

inline int to_int(string s) {int v; istringstream sin(s); sin >> v; return v;}
template<class T> inline string to_str(T x) {ostringstream sout; sout << x; return sout.str();}

typedef long long ll;

int main()
{
	int n,big , small;
	string num;
	cin >> n;
	while(n--)
	{
		cin >> num;
		sort(num.begin(), num.end());
		small = to_int(num);
		sort(num.begin(), num.end(), greater<char>() );
		big = to_int(num);
		cout << big - small << endl;
	}
}

Measured memory_bytes: 1236
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
/*
//#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
*/

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
/*
//#if __cplusplus >= 201103L
#include <array>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
*/
using namespace std;
#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl

#define uni(x) x.erase(unique(all(x)),x.end())
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;

#define INF INT_MAX/3
#define MAX_N 1000
#define M_INF 1000000000
int n,m,v,i;
bool solve(){
   cin.tie(0);
  ios::sync_with_stdio(false);
  cin>>n;
  std::vector<ll> p(n);
  rep(i,n) {
    cin>>p[i];
  }
  cin>>m;
  std::vector<ll> vec(m);
  rep(i,m){
    cin>>vec[i];
  }
  sort(all(p));
  sort(all(vec));
  ll a=0,b=0;
  while(true){
    // cout<<p[a]<<" "<<vec[b]<<endl;
    if(p[a]==vec[b]){
      a++;b++;
    } else if(p[a] != vec[b]){
      a++;
    }
    if(a==n || b == m) break;
  }

  if(b==m) return true;
  else return false;

}

int main(){
  if(solve()) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
  return 0;
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

int main(){
    ll N;
    cin >> N;
    vector<pll> X(N), Y(N);
    REP(i, N){
        cin >> X[i].first;
        X[i].second = i;
    }
    sort(X.begin(), X.end());
    REP(i, N){
        Y[i].first = X[i].second;
        Y[i].second = i;
    }
    sort(Y.begin(), Y.end());
    REP(i, N){
        ll res;
        Y[i].second < N/2 ? res = X[N/2].first : res = X[N/2-1].first;
        cout << res << endl;
    }
    return 0;
}

Measured memory_bytes: 8448
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <utility>
#include <cmath>
using namespace std;

typedef long long llong;
typedef unsigned long long ullong;
// -2.1e-9 <= int <= 2.1e9
// -9.2e-18 <= long long <= 9.2e18
// 0 <= unsigned int <= 4.2e9
// 0 <= unsigned long long <= 18.4e18
// cout << fixed << setprecision(10);

int main() {
    int N;
    cin >> N;
    unordered_map<string, int> C;
    C["AC"] = 0;
    C["WA"] = 0;
    C["TLE"] = 0;
    C["RE"] = 0;
    for (int i=0; i<N; ++i) {
        string s;
        cin >> s;
        C[s]++;
    }

    cout << "AC x " << C["AC"] << endl;
    cout << "WA x " << C["WA"] << endl;
    cout << "TLE x " << C["TLE"] << endl;
    cout << "RE x " << C["RE"] << endl;
}


Measured memory_bytes: 3628
#include<iostream>
#include<map>
#include<cstdio>
#include<cstring>
#define N 40011
#define delta N/2
using namespace std;
char s[8001]={};
int n,tx,ty,m;
int a[8001];
int a1[8001]={},a2[8001]={};
int now,pre;
bool f[2][N],ans1,ans2;
int n1,n2;
int main(void)
{
//freopen("input.txt","r",stdin);
s[1]='T';
scanf("%s%d%d",s+2,&tx,&ty);
n=strlen(s+1);
tx+=delta;
ty+=delta;
m=0;
for(int i=1;i<=n;i++)
	s[i]=='T'?++m:++a[m];
swap(n,m);
n1=n2=0;
for(int i=1;i<=n;i+=2)
	{
	a1[++n1]=a[i];
	a2[++n2]=a[i+1];
	}
now=0,pre=!now;
memset(f,0,sizeof(f));
f[now][delta+a1[1]]=1;
for(int i=2;i<=n1;i++)
	{
	now^=1,pre=!now;
	for(int j=delta-m;j<=delta+m;j++)
		f[now][j]=f[pre][j-a1[i]]|f[pre][j+a1[i]];
	}
ans1=f[now][tx];
now=0,pre=!now;
memset(f,0,sizeof(f));
f[now][delta]=1;
for(int i=1;i<=n2;i++)
	{
	now^=1,pre=!now;
	for(int j=delta-m;j<=delta+m;j++)
		f[now][j]=f[pre][j-a2[i]]|f[pre][j+a2[i]];
	}
ans2=f[now][ty];
if(ans1&&ans2)
	puts("Yes");
else puts("No");
return 0;
}


Measured memory_bytes: 512
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
using System.Numerics;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            Solve();
            //Out.Flush();
            Read();
        }

        static void Solve()
        {
            var N = Sarray()[0];
            WriteLine($"ABC{N:D3}");
        }

        static long Mod = (long)1e9 + 7;
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static public (T1 a, T2 b) Slice<T1, T2>()
        {
            var t = ReadLine().Split();
            return (
            (T1)Convert.ChangeType(t[0], typeof(T1)),
            (T2)Convert.ChangeType(t[1], typeof(T2)));
        }
        static public (T a, T b) Slice2<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)));
        }
        static public (T a, T b, T c) Slice3<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)),
            (T)Convert.ChangeType(t[2], typeof(T)));
        }
    }
}

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

using namespace std;

#define forn(a, e) for (int a = 0; a < (int)(e); a++)
#define forr(a, s, e) for (int a = s; a < (int)(e); a++)
#define fore(e, a) for (auto& e : a)

#ifdef LOCAL
#define logv(a) {cerr << #a << " = "; fore(e, a) {cerr << e << " ";} cerr << "\n";}
#define logvp(a) {cerr << #a << " = "; fore(e, a) {cerr << "(" << e.first << ", " << e.second << ") ";} cerr << "\n";}
#define logvv(a) {cerr << #a << " = \n"; fore(r, a) { fore(e, r) {cerr << e << " ";} cerr << "\n";} }
#define logvf(a, field) {cerr << #a"."#field << " = \n"; fore(e, a) { cerr << e.field << " ";} cerr << "\n"; }
#define logs(a) cerr << #a << " = " << (a) << "\n";
#define logss(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << "\n";
#define logp(a) cerr << #a << " = " << "(" << a.first << ", " << a.second << ")" << "\n";
#define cond(pred, stmt) if (pred) { stmt }
#else
#define logv(a)
#define logvp(a)
#define logvv(a)
#define logvf(a, field)
#define logs(a)
#define logss(a, b)
#define logp(a)
#define cond(pred, stmt)
#endif

using i64 = long long;
using iip = pair<int, int>;
using ivec = vector<int>;
using llvec = vector<i64>;
using svec = vector<string>;

template<typename T, typename Dim>
auto make_vec(T value, Dim dim) { return vector<T>(dim, value); }
template<typename T, typename Dim1, typename... Dim>
auto make_vec(T value, Dim1 dim1, Dim... dims) { return make_vec(make_vec(value, dims...), dim1); }

template<typename T>
bool uax(T& v, const T& newv) { if (v < newv) { v = newv; return true; } else return false; }
template<typename T>
bool uin(T& v, const T& newv) { if (v > newv) { v = newv; return true; } else return false; }

template<typename T>
istream& operator>>(istream& is, vector<T>& c) { for (auto& e : c) is >> e; return is; }

// template<typename ...T>
// istream& read(T&... args) { return (cin >> ... >> args); }

static mt19937 rande(123123);
template<typename T>
T rand_int(T from, T to) { uniform_int_distribution<T> distr(from, to); return distr(rande); }

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

    int a, b;
    while (cin >> a >> b) {
        if (a >= 13) {
            cout << b << endl;
        } else if (a > 5) {
            cout << b / 2 << endl;
        } else {
            cout << 0 << endl;
        }
    }
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String s=br.readLine().trim();
        long res=0;
        for(int i=0;i<s.length();i++){
            res+=(Integer.parseInt(String.valueOf(s.charAt(i))));
        }
        if(res%9==0){
            System.out.println("Yes");
        }
        else{
            System.out.println("No");
        }





    }







}


Measured memory_bytes: 45756
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <iterator>
#include <set>

using namespace std;


int main() {


    int A, B, C, D;
    cin >> A >> B >> C >> D;

    int i = 0;

    while (A > 0 and C > 0) {
        if (i % 2 == 0) {
            C -= B;
        } else {
            A -= D;
        }
        i += 1;
    }

    if (A <= 0) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }


    return 0;

}

Measured memory_bytes: 3652
v = list(map(int, input().split()))
n = v[0]
k = v[1]

ls = [0] * n
for i in range(k):
    okasi = int(input())
    p = list(map(int, input().split()))
    for j in p:
        ls[j-1] += 1

sum = 0
for i in range(n):
    if ls[i] == 0:
        sum += 1

print(sum)


Measured memory_bytes: 9116
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String s = sc.next();
		sc.close();
		String mae = s.substring(0, s.length() / 2);
		String ato = s.substring(s.length() / 2, s.length());
		if (mae.equals(ato) && s.length() % 2 == 0) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}

	public static int[] arrayInt(Scanner sc, int n) {
		int[] array = new int[n];
		for (int i = 0; i < n; i++) {
			array[i] = sc.nextInt();
		}
		return array;
	}

	public static long[] arrayLong(Scanner sc, int n) {
		long[] array = new long[n];
		for (int i = 0; i < n; i++) {
			array[i] = sc.nextLong();
		}
		return array;
	}

	public static double[] arrayDouble(Scanner sc, int n) {
		double[] array = new double[n];
		for (int i = 0; i < n; i++) {
			array[i] = sc.nextDouble();
		}
		return array;
	}
}


Measured memory_bytes: 21844
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <bitset>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

ll extgcd(ll a,ll b,ll& x,ll& y){
	ll d=a;
	if(b){
		d=extgcd(b,a%b,y,x);
		y-=a/b*x;
	}
	else x=1,y=0;
	return d;
}

ll n;
vl a;

int main(){
	cin>>n;
	if(n==1){
		cout<<1<<endl;
		return 0;
	}
	n*=2;
	ll N=n;
	for(ll i=2;i*i<=n;i++) if(n%i==0){
		ll t=1;
		while(n%i==0) n/=i,t*=i;
		a.push_back(t);
	}
	if(n>1) a.push_back(n);
	ll m=a.size(),res=INF;
	for(int i=0;i<1<<m;i++){
		ll p=1;
		for(int j=0;j<m;j++) if(i&1<<j) p*=a[j];
		ll q=N/p,x,y;
		extgcd(p,q,x,y);
		x*=-1;
		if(x>0){
			if(p>INF/x+2) continue;
			res=min(res,p*x);
		}
	}
	cout<<res<<endl;
}

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

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

    int ans = 0;
    for(int i = 1; i <= n; i++){
        int l, r;
        cin >> l >> r;
        int number = r - l +1;
        ans += number;
    }
    printf("%d", ans);
}

Measured memory_bytes: 256
from numba import njit

@njit("i8(i8)")
def loop(i):
    ans = 0
    N = int((i*2)**(1/2))+1
    for j in range(1,N+1):
        for k in range(1,j+1):
            for l in range(1, k+1):
                if (j+k)**2 + (k+l)**2 + (l+j)**2 == 2*i:
                    if j==k==l:
                        ans += 1
                    elif j > k > l:
                        ans += 6
                    else:
                        ans += 3
                if (j+k)**2 + (k+l)**2 + (l+j)**2 >= 2*i:
                    break
            if (j+k)**2 > 2*i:
                break
    return(ans)

n = int(input())
for i in range(1,n+1):
    print(loop(i))

Measured memory_bytes: 110844
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  string tmp;
  cin>>tmp;
  int num;
  num =tmp.size();
  if(tmp.at(num-1)=='s'){
 	cout << tmp+"es" << endl;
  }else{
 	 cout << tmp+"s" << endl;
  }
}

Measured memory_bytes: 3620
while 1:
    n, m = map(int, input().split())
    if n == 0:
        break

    s = [i for i in range(1, n + 1)]

    ind = n - 1
    while len(s) > 1:
        ind = (ind + m) % len(s)
        s.pop(ind)
        ind -= 1
    print(s[0])



Measured memory_bytes: 5608
// edpc_e
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    ll N, W;
    cin >> N >> W;

    vector<ll> w(N), v(N);
    REP(i, N) cin >> w[i] >> v[i];

    ll max_V = 1e5+1;
    vector<ll> dp(max_V+1, numeric_limits<ll>::max());
    dp[0] = 0;
    REP(i, N){
        REP_REV(j, max_V+1){
            if (j - v[i] < 0) break;
            if (dp[j - v[i]] == numeric_limits<ll>::max()) continue;
            dp[j] = min(dp[j], dp[j - v[i]] + w[i]);
        }
    }

    ll ans = 0;
    REP_REV(j, max_V+1){
        if (dp[j] <= W) {
            ans = j;
            break;
        }
    }
    print(ans);


    return 0;
}


Measured memory_bytes: 1024
d,n = map(int, input().split())
 
if d == 0:
    if n < 100:
        print(n)
    else:
        print(101)    
elif d == 1:
    if n < 100:
        print(n*100)
    else:
        print(10100)
elif d == 2:
    if n < 100:
        print(n*10000)
    else:
        print(n*10000+10000)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(x) x.begin(), x.end()
#define mod 1000000007
typedef long long ll;

int main() {
    int k, n;
    cin >> k >> n;
    vector<int> vec;
    rep(i, n){
        int num;
        cin >> num;
        vec.push_back(num);
    }
    int longest = 0;
    rep(i, n-1){
        longest = max(longest, vec[i+1]-vec[i]);
    }
    longest = max(longest, vec[0]+k-vec[n-1]);
    cout << k-longest << endl;
    return 0;
}

Measured memory_bytes: 1400
/* 
	Author: ankrypt
*/


#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int

ll N;
ll A, B;
ll ind[1500005]; 
ll val;
ll curr;
std::vector<ll> adj[1500005];

ll mapping(ll A, ll B) {
	ll X = min(A, B);
	ll Y = max(A, B);
	return X * 1000 + Y;
}


int main() {
	scanf("%lld", &N);
	for(int i = 1; i <= N; i++) {
		scanf("%lld", &val);
		curr = val;
		for(int j = 0; j < N - 2; j++) {
			scanf("%lld", &val);
			adj[mapping(i, curr)].push_back(mapping(i, val));
			curr = val;
			ind[mapping(i, val)]++;
		}
	}
	std::vector<ll> temp;

	for(int i = 1; i <= 1000005; i++) {
		if(!ind[i]) {
			temp.push_back(i);
		}
	}

	ll day = 0, check = 0 ;
	while(!temp.empty()) {
		day++;
		vector<ll> newTemp;
		check += temp.size();
		for(int i = 0; i < temp.size(); i++) {
			for(int j = 0; j < adj[temp[i]].size(); j++) {
				ind[adj[temp[i]][j]]--;
				if(!ind[adj[temp[i]][j]]) {
					newTemp.push_back(adj[temp[i]][j]);
				}
			}
		}
		temp = newTemp;
	}
	// cout << day << " " << check << " ";
	if(check != 1000005) {
		printf("-1\n");
	}
	else {
		printf("%lld\n", day);
	}

	return 0;
}
/*
	Powered by Buggy Plugin
*/


Measured memory_bytes: 64500
N=int(input())
x=[]
for i in range(200):
    x.append(0)
for i in range(200):
    ori=i
    while ori!=0:
        if ori%2==0:
            ori=ori/2
            x[i]+=1
        else:
            break
maxi=1
maxv=0
for i in range(200):
    if maxv<x[i] and i<N+1:
        maxv=x[i]
        maxi=i
print(maxi)


Measured memory_bytes: 3316
#include <stdio.h>
#define N 101
int main(void){
  int i,ct=0;
  char s[N]={},fc,ec;
  scanf("%s",s);
  fc=s[0];
  for(i=0;;i++){
    if(s[i]==0){
      ec=s[i-1];
      ct=i-2;
      break;
    }
  }
  printf("%c%d%c\n",fc,ct,ec);
  return 0;
}


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

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

  int plg = 1;
  int ans = 0;
  while ( b > plg ) {
    plg += a-1;
    ans++;
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3604
from itertools import product
N = int(input())

keta = len(str(N))
# print('keta:',keta)

count=0
for i in range(3,keta+1):
    a = ["7","5","3"]
    As = list(product((a), repeat=i))
    for A in As:
        # print('A:',A)
        if ("3" in A) and ("5" in A) and ("7" in A):
            S = int("".join(A))
            if S <=N:
                count+=1

print(count)


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

using ll = long long;

// greatest common divisor (最大公約数)
ll GCD(ll a, ll b) { return b ? GCD(b, a%b) : a; }

int main(){
  
  // input
  
  ll a,b; cin>>a>>b;          // a, bの上限は10^12であることに注意
  
  // solution
  
  ll G=GCD(a,b);

  ll ans=1;                   // a, bがどのような値でも、1は必ず選ぶことができる
  
  for(ll i=2; i*i<=G; i++){   // √Gまでループを行い素因数判定を行う
    
    if(G%i==0){               // 素因数判定
      ans++;
      while(G%i==0) G/=i;     // Gの素因数からiを除外していく
    }
    
  }
  
  if(G!=1) ans++;             // √Gのループを抜けた時Cが1でないならば、その時のGは素数である
  
  cout<<ans<<endl;
  
}

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

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

int cnt[200000];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	long long ans=0;
	string s;
	cin>>s;
	if(s.size()<3) {
		cout<<"0\n";
		return 0;
	}
	if(s[0]=='A') cnt[0]=1;
	if(s[1]=='A') cnt[1]=cnt[0]+1;
	for(int i=2;i<s.size();i++) {
		if(s[i]=='A') cnt[i]=cnt[i-1]+1;
		else if(s[i-1]=='B' && s[i]=='C') {
			ans+=cnt[i-2];
			cnt[i]=cnt[i-2];
			if(cnt[i]) s[i]='A';
		}
	}
	cout<<ans<<'\n';
	return 0;
}

Measured memory_bytes: 1300
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner f = new Scanner(System.in);
        // fill in the dictionary with the initial value
        int[] values = new int[6];
        for(int i = 0; i < 6; i++){
            values[i] = f.nextInt();
        }
        Dice dice = new Dice(values);
        String movements = f.nextLine();
        String movements2 = f.nextLine();
        char[] s = movements2.toCharArray();
        for(char direction : s){
            dice.roll(direction);
        }
        System.out.println(dice.getTop());
    }
}

class Dice {
    int one;
    int two;
    int three;
    int four;
    int five;
    int six;
    public Dice(int[] values){
        this.one = values[0];
        this.two = values[1];
        this.three = values[2];
        this.four = values[3];
        this.five = values[4];
        this.six = values[5];
    }

    public void roll(char s){
        switch (s){
            case 'E': this.east(); break;
            case 'W': this.west(); break;
            case 'S': this.south(); break;
            case 'N': this.north(); break;
        }
    }

    public void east(){
        int temp = this.six;
        this.six = this.three;
        this.three = this.one;
        int temp2 = this.four;
        this.four = temp;
        this.one = temp2;
    }

    public void west(){
        int temp = this.six;
        this.six = this.four;
        this.four = this.one;
        int temp2 = this.three;
        this.three = temp;
        this.one = temp2;
    }

    public void south(){
        int temp = this.two;
        this.two = this.one;
        this.one = this.five;
        int temp2 = this.six;
        this.six = temp;
        this.five = temp2;
    }

    public void north(){
        int temp = this.two;
        this.two = this.six;
        this.six = this.five;
        int temp2 = this.one;
        this.one = temp;
        this.five = temp2;
    }

    public int getTop(){
        return this.one;
    }
}


Measured memory_bytes: 26376
#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
	int x;
	scanf("%d",&x);
	if(x>=400&&x<=599)
	printf("8");
	else if(x>=600&&x<=799)
	printf("7");
	else if(x>=800&&x<=999)
	printf("6");
	else if(x>=1000&&x<=1199)
	printf("5");
	else if(x>=1200&&x<=1399)
	printf("4");
	else if(x>=1400&&x<=1599)
	printf("3");
	else if(x>=1600&&x<=1799)
	printf("2");
	else if(x>=1800&&x<=1999)
	printf("1");
	return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define REPR(i,n) for (ll i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (ll i = m; i < n; ++i)
#define FORR(i,m,n) for (ll i = n-1; i >= m; --i)
#define FORE(x,xs) for (const auto& x : xs)
#define ALL(v) v.begin(), v.end()

const int MAX = 2e5+10;

int N;

int main() {
    cin >> N;
    ll mn = 1e10;
    ll ans = 0;

    REP (i, N) {
        int a;
        cin >> a;
        if (a < mn) {
            ans++;
            mn = a;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
    int a[] = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };
    int k;
    cin >> k;
    cout << a[k - 1] << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define what_is(x) cerr << #x <<" is " << x << endl;
typedef long long ll;
const int MOD = 998244353;
const double PI = 3.141592653589793;
const ll INF =  1e18 + 7;
const int nax = 200005;


double power(double a, ll b) {
	double ans = 1;
	while (b) {
		if (b & 1) {
			ans = (ans * a);
		}
		a = (a * a);
		b = b >> 1;
	}
	return ans;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tc = 1;
	// cin >> tc;
	while (tc--) {
		ll a, b, n;
		cin >> a >> b >> n;
		if (n < b) {
			ll ans = (n * a) / b - a * (n / b);
			cout << ans;
		}
		else {
			n = b - 1;
			ll ans = (n * a) / b - a * (n / b);
			cout << ans;
		}
		// for (int i = 1; i <= n; i++) {
		// 	// what_is(i);
		// 	// what_is((i * a) / b);
		// 	// what_is(a * (i / b));
		// 	ll x = (i * a) / b - a * (i / b);
		// 	what_is(x);
		// 	// what_is("\n");
		// }

	}
	return 0;
}




















Measured memory_bytes: 3612
#include <iostream>
using namespace std;
int main(){
  
  int a,b;
    for(int i=0;i<999999;i++){
        cin >> a >> b;
        if(a==0 && b==0){
            break;
        }
        for(int j=0;j<a;j++){
            for(int k=0;k<b;k++){
            cout << "#";
        }
        cout << endl;
    }
    cout << endl;
    }
}


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

const int mod = 998244353;

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> l(k), r(k);
	rep(i, k) cin >> l[i] >> r[i];
	vector<ll> dp(n + 1);
	vector<ll> dps(n + 1);
	dp[1] = 1;
	dps[1] = 1;
	for (int i = 2; i <= n; i++) {
		rep(j, k) {
			int li = i - r[j];
			int ri = i - l[j];
			if (ri < 0) continue;
			li = max(li, 1);
			dp[i] += (dps[ri] - dps[li - 1] + mod) % mod;
		}
		dps[i] = (dps[i - 1] + dp[i] + mod) % mod;
	}
	cout << (dp[n] + mod) % mod << endl;
	return 0;
}


Measured memory_bytes: 6412
<?php

fscanf(STDIN, "%d", $n);

if ($n < 10) {
    $b = $n;
} else if ($n < 100) {
    $b = $n % 10;
} else {
    $b = $n % 10;
    $b = $n % 10;
}

switch ($b) {
case 2:
case 4:
case 5:
case 7:
case 9:
    echo 'hon';
    break;
case 0:
case 1:
case 6:
case 8:
    echo 'pon';
    break;
case 3:
    echo 'bon';
}



Measured memory_bytes: 16132
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
B = [a-i-1 for i,a in enumerate(A)]
ctr = Counter(B)
st = sorted(list(ctr.items()))

left = l_sum = 0
ans = r_sum = sum([(k - st[0][0])*v for k,v in st[1:]])

for (k1,v1),(k2,v2) in zip(st,st[1:]):
    left += v1
    l_sum += left * (k2-k1)
    right = N-left
    r_sum -= right * (k2-k1)
    ans = min(ans, l_sum + r_sum)
print(ans)

Measured memory_bytes: 56032
from itertools import accumulate

n=int(input())
s=input()

white=[]
black=[]
w=0
b=0

for i in range(n):
    if s[i]==".":
        w+=1
    else:
        b+=1
    white.append(w)
    black.append(b)

if white==[] or black==[]:
    print(0)
    exit()

MIN=min(white[-1],black[-1])
for i in range(n):
    MIN=min(MIN,black[i]+white[-1]-white[i])
print(MIN)

Measured memory_bytes: 12836
// no proof is included. may have unused libraries. may have unused variables. possibly dirty code - contest mode

#include <iostream> // std::cin, std::cout
#include <cstring> // std::memset()
#include <algorithm> // std::max_element(), std::min_element(), std::reverse(), std::sort(), std::__gcd()

using namespace std;

bool debug = true;

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

    int a, b;
    cin >> a >> b;
    if (a < b) {
        for (int i = 0; i < b; i++) {
            cout << a;
        } cout << endl;
    } else {
        for (int i = 0; i < a; i++) {
            cout << b;
        } cout << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define P pair<ll, ll>
#define Graph vector<vector<ll>>
#define fi first
#define se second
constexpr ll mod = 1000000007;
constexpr ll INF = (1ll << 60);
constexpr double pi = 3.14159265358979323846;
template <typename T>inline bool chmax(T &a, T b){if (a < b){a = b;return 1;}return 0;}
template <typename T>inline bool chmin(T &a, T b){if (a > b){a = b;return 1;}return 0;}

int main(){
    ll ans=INF,n;cin>>n;
    vector<ll> a(n);
    rep(i,n) cin>>a[i];

    
    for(ll i=-100;i<=100;i++){
        ll sum=0;
        rep(j,n){
            sum+=(a[j]-i)*(a[j]-i);
        }

        chmin(ans,sum);
    }

    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 3580
#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(){
    ll N, C; cin >> N >> C;
    vector<ll> x(N+2, 0), v(N+2, 0);
    for(int i=1; i<=N; ++i) cin >> x[i] >> v[i];
    x[N+1] = C;
    ll ans = 0;

    vector<ll> cumv(N+2, 0), f1(N+1, 0), g1(N+1, 0), f2(N+1, 0), g2(N+1, 0);
    for(int i=1; i<=N+1; ++i) cumv[i] = cumv[i-1] + v[i];


    for(int i=1; i<=N; ++i){
        f1[i] = cumv[i] - x[i];
        g1[i] = max(g1[i-1], f1[i]);
        f2[i] = cumv[i] - 2*x[i];
        g2[i] = max(g2[i-1], f2[i]);
    }

    for(int b=1; b<=N+1; ++b){
        // in case of walking OA+2OB
        chmax(ans, cumv[N]-cumv[b-1]-2*(C-x[b])+g1[b-1]);

        // in case of walking 2OA+OB
        chmax(ans, cumv[N]-cumv[b-1]-(C-x[b])+g2[b-1]);
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,m,n) for(int i=m;i<n;i++)
ll mod=1e9+7;

ll power(ll x,ll n){
    if(n==0) return 1;
    ll res=power(x*x%mod,n/2);
    if(n&1) res=res*x%mod;
    return res;
}

int main(){
  int n,k;
  cin>>n>>k;
  cout<<k*power(k-1,n-1)<<endl;
}


Measured memory_bytes: 256
def agc036_a():
    S = int(input())
    x1 = y1 = 0
    x2 = 10**9
    y2 = 1
    d, m = divmod(S, x2)
    if m == 0:
        y2 = x3 = 0
        y3 = d
    else:
        x3 = x2 - m
        y3 = d + 1
    ans = [x1, y1, x2, y2, x3, y3]
    print(*ans, sep=' ')

agc036_a()

Measured memory_bytes: 3060
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
bool use[10];
int main()
{
    int a[4],b[4];
    while(~scanf("%d%d%d%d",&a[0],&a[1],&a[2],&a[3])){
        memset(use,0,sizeof(use));
        for(int i=0;i<4;i++) use[a[i]]=1;
        scanf("%d%d%d%d",&b[0],&b[1],&b[2],&b[3]);
        int aa=0,bb=0;
        for(int i=0;i<4;i++){
            if(a[i]==b[i]) aa++;
            else if(use[b[i]]) bb++;
        }
        cout<<aa<<" "<<bb<<endl;
    }
    return 0;
}

Measured memory_bytes: 1208
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define mod 1000000007

int main()
{
	ll n,m,x,y,r,a,b,i;
     cin>>n>>m>>a>>b;
     x=INT_MIN,y=INT_MAX;
     for(i=0;i<n;i++)
     {
          cin>>r;
          x=max(x,r);
     }
     for(i=0;i<m;i++)
     {
          cin>>r;
          y=min(y,r);
     }
     if(x<y and (y>a and x<b))
     std::cout << "No War" << '\n';
     else
     std::cout << "War" << '\n';
}


Measured memory_bytes: 256
package main

import (
	"fmt"
	"bufio"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)
func scanInt() int {
	sc.Scan()
	a,_ := strconv.Atoi(sc.Text())
	return a
}

func scanText() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	sc.Split(bufio.ScanWords)
	
	n := scanInt()
	f := true
	pre := 0
	for i := 0; i < n; i++ {
		now := scanInt()
		if pre <= now -1 {
			pre = now - 1
		} else if pre <= now {
			pre = now
		} else {
			f = false
		}
	}

	if f {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 2304