akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;
#define int long long
using ld = long double;

signed main() {
    int n;
    cin >> n;
    int arr[n+1], pref[n+1];
    int i, j;
    pref[0] = 0;
    for(i=1;i<=n;i++)
        cin >> arr[i];
    for(i=1;i<=n;i++)
        pref[i] = pref[i-1] + arr[i];
    int dp[n+1][n+1];
    for(i=0;i<=n;i++)
        for(j=0;j<=n;j++)
            dp[i][j] = 1e18;
    for(i=1;i<=n;i++)
        dp[i][i] = 0;
        
    for(int len = 1;len < n;len++)
    {
        for(i=1;i<=(n-len);i++)
        {
            int j = i + len;
            // merge [i, j]
            for(int k = i; k <= j-1;k++)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + pref[j] - pref[i-1]);
        }
    }
    cout << dp[1][n] << '\n';
}


Measured memory_bytes: 4892
//confilm 0LL and 1LL
//confilm cornercases such as 0
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecVec = vector<Vec>;
#define REP(i, m, n) for(ll (i) = (m); (i) < (n); ++(i))
#define REPN(i, m, n) for(ll (i) = (m); (i) <= (n); ++(i))
#define REPR(i, m, n) for(ll (i) = (m); (i) >= (n); --(i))
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPR(i, n, 1)
#define co(n) cout << (n) << endl
#define cosp(n) cout << (n) << ' '
#define setp(n) cout << fixed << setprecision(n);
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fs first
#define sc second
template <typename T>
bool chmax(T &a, const T& b){if(a < b){a = b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T& b){if(a > b){a = b; return true;} return false;}
void sonic(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);}
const ll INF = 1e9+1;
const ll LINF = 1e18+1;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const double PI = acos(-1);
const double EPS = 1e-9;

int main(void){
	ll n;
	cin >> n;
	string s;
	cin >> s;
	Vec cntW(n), cntB(n);
	rep(i, n){
		if(s[i] == '#') cntB[i]++;
		if(i) cntB[i] += cntB[i-1];
	}
	repr(i, n){
		if(s[i] == '.') cntW[i]++;
		if(i < n-1) cntW[i] += cntW[i+1];
	}

	ll ans = min(cntW[0], cntB[n-1]);
	rep(i, n-1) chmin(ans, cntW[i+1]+cntB[i]);
	co(ans);

	return 0;
}


Measured memory_bytes: 3716
#include <bits/stdc++.h>
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() {
  string A,B;
  cin>>A>>B;
  if(A[0]==B[2]&&A[1]==B[1]&&A[2]==B[0]){
    cout<<"YES"<<endl;
  }
  else{
    cout<<"NO"<<endl;
  }
}

Measured memory_bytes: 256
def dist(x,y):
    return abs(x[0]-y[0])+abs(x[1]-y[1])
N = int(input())
X = [list(map(int,input().split())) for _ in range(N)]
X.insert(0,[0,0,0])
flag = 0
for i in range(1,N+1):
    dx = dist(X[i][1:],X[i-1][1:])
    dt = X[i][0]-X[i-1][0]
    if dt>=dx and (dt-dx)%2==0:
        continue
    else:
        flag = 1
        break
if flag==0:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 60504
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A,B;
  cin>>A>>B;
  
  if (A>=13) {
    cout<<B<<endl;
  }
  else if (6<=A&&A<=12) {
    cout<<B/2<<endl;
  }
  else {
    cout<<0<<endl;
  }
  
  
  
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }

typedef long long  ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
    int N;
    int a[110];
    cin>>N;
    REP(i,N) cin>>a[i];
    int cnt=0;
    REP(i,N-1){
        if(a[i]==a[i+1]){
            a[i+1]=100+i;
            cnt+=1;
        }
    }
    cout<<cnt<<endl;

    return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a); i > (b); i--)
#define ALL(a) (a).begin(), (a).end()

int main() {
    ll N, K, a, b;
    cin >> N >> K;

    pii array[100000];
    REP(i, N) {
        cin >> a >> b;
        array[i] = {a, b};
    }
    sort(array, array + N);
    REP(i, N) {
        K -= array[i].second;
        if (K <= 0) {
            cout << array[i].first << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 1024
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=Integer.parseInt(sc.next());
        int k=Integer.parseInt(sc.next());
        int l=Integer.parseInt(sc.next());
        UnionFindTree roads=new UnionFindTree(n);
        for(int i=0;i<k;i++){
            roads.union(Integer.parseInt(sc.next())-1,Integer.parseInt(sc.next())-1);
        }
        UnionFindTree trains=new UnionFindTree(n);
        for(int i=0;i<l;i++){
            trains.union(Integer.parseInt(sc.next())-1,Integer.parseInt(sc.next())-1);
        }
        HashMap<Pair,Integer> map=new HashMap<>();
        for(int i=0;i<n;i++){
            Pair p=new Pair(roads.find(i),trains.find(i));
            if (map.containsKey(p)){
                map.put(p,map.get(p)+1);
            }else{
                map.put(p,1);
            }
        }
        StringBuilder sb=new StringBuilder();
        for (int i=0;i<n;i++){
            if(i!=0){
                sb.append(" ");
            }
            Pair p=new Pair(roads.find(i),trains.find(i));
            sb.append(map.get(p));
        }
        System.out.println(sb);
    }

    static class Pair{
        int x;
        int y;
        public Pair(int x,int y){
            this.x=x;
            this.y=y;
        }
        public int hashCode(){
            return x+y;
        }
        public boolean equals(Object o){
            Pair p = (Pair) o;
            return p.x==x && p.y==y;
        }
    }

    static class UnionFindTree{
        int[] par;
        int[] rank;
        public UnionFindTree(int size){
            this.par=new int[size];
            this.rank=new int[size];
            for(int i=0;i<size;i++){
                makeSet(i);
            }
        }
        public void makeSet(int i){
            par[i]=i;
            rank[i]=0;
        }
        public void union(int x,int y){
            int xRoot=find(x);
            int yRoot=find(y);
            if(rank[xRoot]>rank[yRoot]){
                par[yRoot]=xRoot; 
            }else if(rank[xRoot]<rank[yRoot]){
                par[xRoot]=yRoot;
            }else if(xRoot!=yRoot){
                par[yRoot]=xRoot;
                rank[xRoot]++;
            }
        }
        public int find(int v){
            if (par[v]!=v){
                par[v]=find(par[v]);
            }
            return par[v];
        }
        public boolean same(int x,int y){
            return find(x)==find(y);
        }
    }
}

Measured memory_bytes: 82596
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int,int> pii;
const int maxn=1e5+7;
const ll modn=1e9+7;
const int inf=2e9+7;
const double PI = acos(-1.0);
const double eps=1e-8;
inline int lowbit(int x){return x&-x;}
inline ll lowbit(ll x) {return x&-x;}
inline int CountOneBinary(ll num){int ans=0;while(num){if(num&1) ans+=1;num>>=1;}return ans;}
inline void read(int &x){char c;x=0;for(c=getchar();c>'9'||c<'0';c=getchar());for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';}
inline void read(ll &x){char c;x=0;for(c=getchar();c>'9'||c<'0';c=getchar());for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';}
inline ll qpow(ll x,ll y){ll ans=1;while(y){if(y&1) ans=ans*x%modn;x=x*x%modn;y>>=1;}return ans;}
inline double qpow(double x,ll y){double ans=1;while(y){if(y&1) ans=ans*x;x=x*x;y>>=1;}return ans;}
struct Node
{
    int pos,num;
    bool operator < (const Node &tmp) const
    {
        return num>tmp.num;
    }
};
int n,a[maxn];
Node vis1[maxn],vis2[maxn];
int main()
{
    while(scanf("%d",&n)==1)
    {
        for(int i=0;i<maxn;i++) vis1[i].pos=vis2[i].pos=i,vis1[i].num=vis2[i].num=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(i%2) vis1[a[i]].num++;
            else vis2[a[i]].num++;
        }
        sort(vis1,vis1+maxn);
        sort(vis2,vis2+maxn);
        if(vis1[0].pos!=vis2[0].pos) printf("%d\n",n-vis1[0].num-vis2[0].num);
        else
        {
            int ans=max(vis1[0].num+vis2[1].num,vis1[1].num+vis2[0].num);
            printf("%d\n",n-ans);
        }
    }
}


Measured memory_bytes: 2176
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>

using namespace std;

double EPS = 1e-10;

double add(double a, double b){
  if(abs(a+b) < EPS * (abs(a)+abs(b)))return 0;
  return a+b;
}

struct point{
  double x, y;
  point(){}
  point(double x,double y) : x(x) , y(y){}

  point operator + (point p){
    return point(add(x,p.x), add(y,p.y));
  }

  point operator - (point p){
    return point(add(x,-p.x), add(y,-p.y));
  }

  point operator * (double d){
    return point(x*d,y*d);
  }
};

double cross(point a, point b) {
  return (a.x * b.y - a.y * b.x);
}

int is_intersected_ls(point a1, point a2, point b1, point b2) {
  return ( cross(a2-a1, b1-a1) * cross(a2-a1, b2-a1) < EPS ) &&
         ( cross(b2-b1, a1-b1) * cross(b2-b1, a2-b1) < EPS );
}

int main(void){
  int n;
  point p[3],k,s;

  cin >> n;
  while(n--){
    for(int i=0;i<3;i++)
      cin >> p[i].x >> p[i].y;
    
    cin >> k.x >> k.y >> s.x >> s.y;
    int cnt=0;
    for(int i=0;i<3;i++)
      for(int j=i+1;j<3;j++)
	if(i!=j)
	  cnt+=is_intersected_ls(p[i],p[j],k,s);
    
    if(cnt%2)cout << "OK" << endl;
    else cout << "NG" << endl;
    
  }

  return 0;
}

Measured memory_bytes: 952
//やりなおし
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)

int main()
{
    ll n, q;
    vector<ll> a, b, m, e;
    cin >> n;
    a.resize(n);
    for (auto &x : a)
        cin >> x;

    cin >> q;
    b.resize(q);
    m.resize(q);
    e.resize(q);
    rep(i, q)
    {
        cin >> b[i] >> m[i] >> e[i];
        rotate(a.begin() + b[i], a.begin() + m[i], a.begin() + e[i]);
    }

    rep(i, n) cout << ((i) ? " " : "") << a[i];
    cout << endl;

    return 0;
}


Measured memory_bytes: 3152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(int i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(int i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define uniq(x) (x).erase(unique((x).begin(), (x).end()), (x).end())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int m, d;
    cin >> m >> d;
    int ans = 0;
    
    reps(i, 1, m + 1) {
        reps(ii, 1, d + 1) {
            int one = ii % 10;
            int ten = ii / 10;
            
            if ((one >= 2) && (ten >= 2) && ((one * ten) == i)) {
                ans++;
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
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 = sc.nextInt();
		int arr[] = new int[n];
		for(int i=0 ; i<n ; i++){
			arr[i] = sc.nextInt();
		}
		long num = 0;
		long num2 = 0;
		int count = 1;
		Arrays.sort(arr);
		for(int i=n-1 ; i>=1 ; i--){
			if(arr[i]==arr[i-1]){
				count++;
				if(num==0){
					num = arr[i];
				}
				if(num!=arr[i]){
					num2 = arr[i];
				}
				if(count>=4){
					num2 = arr[i];
				}
			}else{
				continue;
			}
			if(num!=0 && num2!=0){
				break;
			}
			
		}
		
		System.out.println(num*num2);
	}
}

Measured memory_bytes: 48712
#include <bits/stdc++.h>
#define FOR(i, m, n) for (ll i = m; i < (n); i++)
#define RFOR(i, m, n) for (ll i = (m - 1); i >= 0; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define print(ele) cout << (ele) << "\n"
#define print10(ele) cout << fixed << setprecision(10) << (ele) << "\n"

using namespace std;
typedef long long ll;
typedef vector<int> ivec;
typedef vector<string> svec;
typedef vector<ll> lvec;

const int mod = 1e9 + 7;
const ll INF = 1000000000000000000LL;

int main() {
  int n, m, x;
  cin >> n >> m >> x;
  ivec a(m);
  REP(i, m) cin >> a[i];
  int ansA = 0;
  RFOR(i, x, 0) {
    REP(j, m) {
      if (i == a[j]) ansA++;
    }
    }
  int ansB = 0;
  FOR(i, x, n) {
    REP(j, m) {
      if (i == a[j]) ansB++;
    }
  }
  print(min(ansA, ansB));
  return 0;
}

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

int T[2],R[2];
int main(){
    cin >> T[0] >> T[1] >> R[0] >> R[1];
    if(R[0]>-1 && R[1]>-1){
        if(R[0]==R[1]) cout << "Draw" << endl;
        else cout << (R[0]>R[1]? "Alice":"Bob") << endl;
    }else{
        if(T[0]==T[1]) cout << "Draw" << endl;
        else cout << (T[0]>T[1]? "Bob":"Alice") << endl;
    }
}


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

int main() {
  ll a;
  cin >> a;
  if(a==1) cout << 0 << endl;
  else cout << 1 << endl;
  
  return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
#define pb push_back
#define f(i,n) for(i=0;i<n;i++)
#define F(i,a,b) for(i=a;a<=b;i++)
#define arr(a,n) for( i=0;i<n;i++)cin>>a[i];
#define fi first
#define se second
#define mp make_pair
#define mod 1000000007
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define vi vector<ll>
#define ed end()
#define bg begin()
#define sz size()
#define ln length()
#define s() sort(a,a+n);
#define sr() sort(a,a+n,greater<ll>());
#define v()  sort(v.begin(),v.end());
#define vr() sort(v.begin(),v.end(),greater<ll>());
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll power(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
int main() {
/*		#ifndef ONLINE_JUDGE
	    // for getting input from input.txt
	    freopen("input.txt", "r", stdin);
	    // for writing output to output.txt
	    freopen("output.txt", "w", stdout);
	#endif*/
fast();
//ll  t;cin>>t;while(t--)
{
	ll n,s=0;
	cin>>n;
	ll a[n];
	for( int i=0;i<n;i++)
	      cin>>a[i];

	sr()
	for(int i=1;i<n;i++)
	{
        s+=a[i];
	}

if(a[0]<s)
	Yes
else
	No
	

}
return 0;
}

Measured memory_bytes: 256
#include<vector>
#include<algorithm>
#include<iostream>
int main (){
    std::cin.tie(0); 
	std::ios::sync_with_stdio(false);

    int N,K;std::cin>>N>>K;
    std::vector<int> p(N,0);
    for (int i=0;i<N;++i){
        std::cin>>p[i];
    }
    std::sort(p.begin(),p.end());
    int ans=0;
    for(int i=0;i<K;++i){
        ans+=p[i];
    }
    std::cout<<ans;
    return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N, K, D;
    int like[10] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};


    cin >> N >> K;

    for(int i = 0;i < K; ++i) { // 1 is considered true
        cin >> D;
        like[D] = 0; // dislike a number
    }

    int flag = false;
    for(int i = N;i < 100000; ++i) {
        string sN = to_string(i);
        for(int j = 0;j < sN.size(); ++j) { // per number like/not
            int indx = int(sN[j] - 48);
            if(like[indx] == 0) {
                break;
            } else if(j == sN.size() - 1) {
                flag = true;
            }
        }
        if(flag) {
            cout << i;
            break;
        }
    }

}


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

namespace AtCoder
{
	public class Program
	{
		static int[] h;

		static Dictionary<int, long> dp = new Dictionary<int, long>();

		static void Main(string[] args)
		{
			int n = int.Parse(Console.ReadLine());
			h = Console.ReadLine().Split().Select(int.Parse).ToArray();
			dp[0] = 0;

			Console.WriteLine(Compute(n - 1));
		}

		static long Compute(int index)
		{
			if (dp.ContainsKey(index)) {
				return dp[index];
			}

			long cost1 = Compute(index - 1) + Math.Abs(h[index - 1] - h[index]);
			long cost2 = long.MaxValue;
			if (index >= 2) {
				cost2 = Compute(index - 2) + Math.Abs(h[index - 2] - h[index]);
			}
			dp[index] = Math.Min(cost1, cost2);
			return dp[index];
		}

	}
}

Measured memory_bytes: 31840
from collections import defaultdict

N, K = map(int, input().split())
A = map(int, input().split())

Am = [a - 1 for a in A]
Acc = [0] * (N + 1)
for i in range(N):
    Acc[i + 1] = (Acc[i] + Am[i]) % K

d = defaultdict(int)
l, r = 0, 0
ans = 0
while r <= N:
    a = Acc[r]
    ans += d[a]
    d[a] += 1
    r += 1
    if r - l >= K:
        d[Acc[l]] -= 1
        l += 1
print(ans)


Measured memory_bytes: 41224
#include<stdio.h>

int main(){
  long l[87];
  l[0]=2;
  l[1]=1;
  int i;
  int n;
  scanf("%d",&n);
  if(n<=86&&n>=1){
    for(i=2;i<=n;i++)
      l[i]=l[i-1]+l[i-2];
    printf("%ld\n",l[n]);
  }
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i = (l); i < (r); ++i)
using ll = long long;
template<class T,class U>using umap = unordered_map<T,U>;
template<class T>using uset = unordered_set<T>;
template<class T>using max_heap = priority_queue<T>;
template<class T>using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<class T>inline bool Chmax(T&a, const T&b){
  if(b > a){    a = b;    return true;  }
  return false;
}
template<class T>inline bool Chmin(T&a, const T&b){
  if(a > b){    a = b;    return true;  }
  return false;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;cin >> n;
  vector<pair<int,int>> v(n);
  rep(i,0,n){
    cin >> v[i].first;
    v[i].second = i+1;
  }
  sort(v.begin(), v.end());
  rep(i,0,n){
    if(i != 0)cout << ' ';
    cout << v[i].second;
  }
  cout<< endl;

  return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
long long dp[200001];
long long pre[200001];
int main()
{
    long long n , k;
    cin >> n >> k;
    vector<pair<long long,long long > >S;
    for(long long i=0; i<k; i++)
    {
        long long l, r;
        cin >> l >> r;
        S.push_back({l,r});
    }
    dp[0]=0;
    dp[1]=1;
    dp[2]=-1;
    for(int i=1; i<=n; i++)
    {
        dp[i] = (dp[i]%mod + dp[i-1]%mod)%mod;
        for(int j=0; j<k; j++)
        {
            int l = S[j].first;
            int r = S[j].second;
            if(i+l<=n)
            {
                dp[i+l] += dp[i];
                dp[i+l]%=mod;
            }
            if(i+r+1<=n)
            {
                dp[i+r+1] = (dp[i+r+1] - dp[i] + mod)%mod;
                dp[i+r+1]%=mod;
            }
        }
    }
    cout << dp[n] << endl;

}


Measured memory_bytes: 5096
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
int x[maxn],xx[maxn],w[maxn];
int i,j,k,l,r,s,t,n,m;
long long c;
int main()
{
    cin>>n>>l>>t;
    for(i=1;i<=n;i++) cin>>x[i]>>w[i];
    for(i=1;i<=n;i++) {
        if(w[i]==2) w[i]=-1;
        r=x[i]+w[i]*t;
        if(r>0) (c+=r/l)%=n;
        else if(r<0) (c+=(r+1)/l-1)%=n;
        xx[i]=(r%l+l)%l;
    }
    sort(xx+1,xx+n+1);
    c=(c+n)%n;
    for(i=c+1;i<=n;i++) printf("%d\n",xx[i]);
    for(i=1;i<=c;i++) printf("%d\n",xx[i]);
}

Measured memory_bytes: 2432
def main():
    def f(s):
        return s
    n=int(input())
    s,t=list(map(f,input().split()))
    ans=""
    for i in range(n):
        ans+=s[i]
        ans+=t[i]
    print(ans)
    


            

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
N,Y=map(int,input().split())
for x in range(N+1):
    for y in range(N+1):
        z=N-x-y
        if 0<=z<=2000:
            if 10000*x+5000*y+1000*z==Y:
                print(x,y,z)
                exit()
print(-1,-1,-1)

Measured memory_bytes: 3060
#include<cstdio>
#include<iostream>
using namespace std;
int n,k;

int main()
{ int a[310000];
    scanf("%d%d",&k,&n);
    if(k&1)
    {
        for(int i=1;i<=n;i++)
            a[i]=(k+1)/2;
        int last=n;
        for(int i=1;i<=n/2;i++)
            if(a[last]==1) last--;
            else
            {
                a[last]--;
                for(int j=last+1;j<=n;j++)
                    a[j]=k;
                last=n;
            }
        for(int i=1;i<=last;i++)
            printf("%d ",a[i]);
    }
    else
    {
        printf("%d ",k/2);
        for(int i=2;i<=n;i++)
            printf("%d ",k);
    }
    return 0;
}


Measured memory_bytes: 3456
a = raw_input().split()
for i in range(3):
	a[i] = int(a[i])

b = a[1] - a[2]
if b >= 0:
	print "delicious"
else:
	if a[0] + a[1] < a[2]:
		print "dangerous"
	else:
		print "safe"

Measured memory_bytes: 2568
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int c[20];
int a[20][20];
int b[20];
int n, m, x, ans;

void check(){
	int d[20];
	memset(d, 0, sizeof(d));
	int cnt = 0;
	for (int i = 1; i <= n; i++){
		if (b[i] == 1){
			for (int j = 1; j <= m; j++){
				d[j] += a[i][j];
			}
			cnt += c[i];
		}
	}
	bool flag = true;
	for (int i = 1; i <= m; i++){
		if (d[i] < x){
			flag = false;break;
		}
	}
	if (flag){
		if (cnt < ans) ans = cnt;
	}
	return;
}

void dfs(int k){
	if (k == n + 1){
		check();
		return ;
	}
	for (int i = 0; i <= 1; i++){
		b[k] = i;
		dfs(k + 1);
	}
}

int main(){
	cin >> n >> m >> x;
	for (int i = 1; i <= n; i++){
		cin >> c[i];
		for (int j = 1; j <= m; j++){
			cin >> a[i][j];
		}
	}
	memset(b, 0, sizeof(b));
	ans = 1 << 30;
	dfs(1);
	if (ans == 1 << 30){
		cout << -1 << endl;
	}
	else{
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 3620
H, W = map(int, input().split())
L = [list(input()) for j in range(H)]
res = []

for w in range(W):
    t = []
    for h in range(H):
        t.append((L[h][w]))
    
    if '#' not in t:
        for h in range(H):
            L[h][w] = ""
            
for l in L:
    if "#" not in l:
        pass
    else:
        res.append(l)

for i in res:
    result = ''
    for j in i:
        result += j
    print(result)

Measured memory_bytes: 3064
def B_CollectingBalls(N, K, x):
    ans = 0
    for i in range(0, N):
        dist = min(abs(x[i]), abs(x[i] - K)) * 2
        ans += dist
    return ans
  
N=int(input())
K=int(input())
x=[int(i) for i in input().split()]
print(B_CollectingBalls(N, K, x))

Measured memory_bytes: 3060
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <unordered_map>
#include <assert.h>
using namespace std;

#define ran(i, a, b) for ((i) = (a); (i) < (b); (i)++)
#define rep(i, a) ran ((i), 0, (a))
#define rep1(i, a) ran ((i), 1, (a)+1)
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef unsigned long long ull;
#define _0 first
#define _1 second
#define _pb(x) push_back(x)
#define _mp(x, y) make_pair(x, y)
#if defined(SHIROKO1_LOCAL) && !defined(NDEBUG)
#define DEBUG(...) fprintf(stderr, "[DEBUG] " __VA_ARGS__)
#else
#define DEBUG(...) ((void)0)
#endif

int main()
{
	int a, b, c;
	cin >> a >> b >> c;
	puts((!(c < a) && !(c > b)) ? "Yes" : "No");
	return 0;
}


Measured memory_bytes: 256
/*
    Reference :-
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define forn1(i, n) for (int i = 1; i < int(n); i++)
//ll mod=1000000007;
ll mod=998244353;
const int N=100001;
int vis[N], hi[N],par[N],ans[N];
vector<int> adj[N];
map<pair<int,int>,int > ma1;
int ma=0,co=0;

ll power(ll n,ll k){
    ll ans=1;
    while(k){
        if(k&1)ans=(ans*n)%mod;
        k/=2;
        n=(n*n)%mod;
    }
    //ans=(ans-1+mod)%mod;
    return ans;
}

int main() {
    //std::ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin>>n;
    forn(i,n-1){
        int a,b;
        cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
        if(a>b)ma1[{b,a}]=i;
        else ma1[{a,b}]=i;
    }
    //int ma=0;
    forn1(i,n+1)ma=max(ma,int(adj[i].size()));
    //cout<<ma<<endl;
    //dfs(1);
    queue<int> que;
    que.push(1);
    int vis[n+1]={0};
    vis[1]=1;
    int par[n+1]={0};
    que.pop();
    forn(i,adj[1].size()){
        que.push(adj[1][i]);
        par[adj[1][i]]=1;
        vis[adj[1][i]]=1;
        ans[ma1[{1,adj[1][i]}]]=co%ma;
        //cout<<ma1[{1,adj[1][i]}]<<" "<<ans[ma1[{1,adj[1][i]}]]<<endl;
        co++;
    }
    while(!que.empty()){
        int s=que.front();
        que.pop();
        int pre=ans[ma1[{par[s],s}]];
        //cout<<pre<<endl;
        int mc=0;
        forn(i,adj[s].size()){
            if(vis[adj[s][i]]==0){
                que.push(adj[s][i]);
                vis[adj[s][i]]=1;
                par[adj[s][i]]=s;
                ans[ma1[{s,adj[s][i]}]]=(pre+mc+1)%ma;mc++;
                //cout<<ma1[{s,adj[s][i]}]<<" "<<ans[ma1[{s,adj[s][i]}]]<<endl;
            }
        }
    }
    cout<<ma<<endl;
    forn(i,n-1)cout<<ans[i]+1<<endl;

	return 0;
}


Measured memory_bytes: 13568
a = list(map(int, input().split()))
five = 0
seven = 0
for i in range(3):
    if a[i] == 5:
        five += 1
    if a[i] == 7:
        seven += 1

if five == 2 and seven == 1:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3060
N = int(input())
A = list(map(int, input().split()))

ans = 0
while sum(list(map(lambda x: x % 2, A))) == 0:
  A = list(map(lambda x: x / 2, A))
  #あるいはリスト内包表記でもOK(上記のmap関数内のlambda関数に比較して、1ms早い)
  #A = [i / 2 for i in A]
  ans += 1 

print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    long long int a,b,n,s;
    cin>>a>>b>>n;
    if(b>n){
    s=floor((a*n)/(b))-a*(floor((n)/(b)));
    }
 
   else if(b<=n){
    s=floor((a*(b-1))/(b));
    }
    cout<<s;
 
}

Measured memory_bytes: 3596
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <numeric>
#include <cstdlib>
#include <map>
#include <algorithm>

using namespace std;

int main(){
    int N;

    cin >> N;

    int fx = 0;
    int X = N;

    while(N > 0){
        fx += N%10;
        N /= 10;
    }

    if(X%fx == 0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
const double PI = acos(-1);
const double EPS = 1e-15;
long long INF=(long long)1E17;
#define i_7 (long long)(1E9+7)
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}

using namespace std;
bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}

long long gcd_(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}
 
class UnionFind {
    public:
    //各頂点の親の番号を格納する。その頂点自身が親だった場合は-(その集合のサイズ)を入れる。
    vector<int> Parent;
    
    //クラスを作るときは、Parentの値を全て-1にする。
    //以下のようにすると全てバラバラの頂点として解釈できる。
    UnionFind(int N) {
        Parent = vector<int>(N, -1);
    }
    
    //Aがどのグループに属しているか調べる
    int root(int A) {
        if (Parent[A] < 0) return A;
        return Parent[A] = root(Parent[A]);
    }
    
    //自分のいるグループの頂点数を調べる
    int size(int A) {
        return -Parent[root(A)];//先祖をrootで取っておきたい。
    }
    
    //AとBをくっ付ける
    bool connect(int A, int B) {
        //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        if (A == B) {
            //すでにくっついてるからくっ付けない
            return false;
        }
        
        //大きい方(A)に小さいほう(B)をくっ付けたい
        //大小が逆だったらAとBをひっくり返す。
        if (size(A) < size(B)) swap(A, B);
        
        //Aのサイズを更新する
        Parent[A] += Parent[B];
        //Bの親をAに変更する
        Parent[B] = A;
        
        return true;
    }
};

int main(){
  
  string s;
  cin>>s;
  int n=s.size();
  vector<int> temp;
  REP(i,n-1){
    if(s[i]!=s[i+1]){
      temp.push_back(max(i+1, n-i-1));
    }
  }
  if(temp.empty()){
    cout<<n<<endl;
  }else{
    sort(temp.begin(), temp.end());
    cout<<temp[0]<<endl;
  }
  
  return 0;
}


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

using namespace std;

int main(){

  int a, b, x;

  cin >> a >> b;

  if ((a + b) % 2 == 0){
    x = (a + b) / 2;
  }else{
    x = ((a + b) / 2) + 1;
  }

  cout << x << endl;


}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

int N,M,ans = 0;
vector<int> dif;

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

	cin >> N >> M;

	if(N >= M){
		cout << "0" << endl;
		return 0;
	}
	vector<int> X(M);
	for(auto &x: X){
		cin >> x;
	}

	sort(X.begin(),X.end());

	REP(i,M - 1){
		dif.push_back(X[i + 1] - X[i]);
	}
 
	sort(dif.rbegin(),dif.rend());

	int sum = 0;
  	REP(i,N - 1){
    	sum += dif[i];
    }
	cout << X[M - 1] - X[0] - sum << endl;

}


Measured memory_bytes: 1276
loop do
    dir = gets.strip.gsub(/north|west/, "north" => "n", "west" => "w")
    break if dir == "\#"
    a = dir[dir.size-1] == "n" ? 0 : 90
    (dir.size-2).downto(0) do |i|
        t = 90.0 / (2**(dir.size-i-1)).to_f
        case dir[i]
        when "n"
            a = a - t
        when "w"
            a = a + t
        end
    end
    if a == a.to_i
        puts a.to_i
    else
        den = 1
        while a != a.to_i
            a *= 2
            den *= 2
        end
        puts "#{a.to_i}/#{den}"
    end
end

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

int main(){
  int n,x,sum=0,ans=0; cin>>n>>x;
  vector<int> a(n);
  for(int i=0; i<n; i++) {
    cin>>a[i];
    sum += a[i];
  }
  x -= sum;
  sort(a.begin(),a.end());
  while(x>=a[0]) {
    x -= a[0];
    ans++;
  }
  cout<<ans+a.size();
}

Measured memory_bytes: 256
def calc_comb(m)
#  if m < 2
#    return 0
#  elsif m == 2 
#    return 1
#  else
    return m * (m - 1) / 2
#  end
end

n = gets.strip.to_i
a = gets.strip.split(' ')

hash = a.group_by(&:itself).map{|key, value|[key, value.count]}.to_h

comb = Hash.new
sum  = 0
hash.each do |k,v|
  comb_res = calc_comb(v)
  comb[k] = comb_res
  sum = sum + comb_res
end

(1..n).each do |i|
  value = comb[a[i-1]]
  new_value = calc_comb(hash[a[i-1]] - 1)
  puts sum - (value - new_value)
end


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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 1e2 + 5;

map<pair<ll, ll>, int > st[2];

char c[MAXN], c1[2][MAXN];

ll mod[2];
ll p[2];
//ll stp[2][MAXN];

void process(int ind, int n){
	ll v[2][2];
	REP(mask, 0, 1 << n){
		REP(i, 0, 2){
			REP(j, 0, 2){
				v[i][j] = 0;
			}
		}
		REP(i, 0, n){
			if (mask & (1 << i)) {
				REP(j, 0, 2){
					v[0][j] = (v[0][j] * p[j] + c1[ind][i]) % mod[j];
				}
			} else {
				REP(j, 0, 2){
					v[1][j] = (v[1][j] * p[j] + c1[ind][i]) % mod[j];
				}
			}
		}
		ll a = (v[0][0] << 32ll) + v[0][1];
		ll b = (v[1][0] << 32ll) + v[1][1];
		st[ind][mp(a, b)]++;
	}
}

void solve(){
	mod[0] = 1000000007;
	mod[1] = 1000000009;
	p[0] = 997;
	p[1] = 257;
	/*REP(i, 0, 2){
		stp[i][0] = 1;
		REP(j, 1, MAXN){
			stp[i][j] = (stp[i][j - 1] * p[i]) % mod[i];
		}
	}*/
	int n;
	scanf("%d%s", &n, &c[0]);
	REP(i, 0, n){
		c1[0][i] = c[i];
		c1[1][i] = c[2 * n - 1 - i];
	}
	
	
	
	process(0, n);
	process(1, n);
	ll ans = 0ll;
	
	//return;
	
	FA(it, st[0]){
		if (st[1].find(it->_1) != st[1].end()) {
			ans += (ll)st[1][it->_1] * (ll)it->_2;
		}
	}
	
	/*printf("%s\n", c1[0]);
	FA(it, st[0]){
		printf("%lld %lld %lld %lld %d\n", it->_1._1 >> 32ll, it->_1._1 % (1ll << 32ll), it->_1._2 >> 32ll, it->_1._2 % (1ll << 32ll), it->_2);
	}
	printf("##########\n");
	printf("%s\n", c1[1]);
	FA(it, st[1]){
		//ans += st[1][it->_1];
		printf("%lld %lld %lld %lld %d\n", it->_1._1 >> 32ll, it->_1._1 % (1ll << 32ll), it->_1._2 >> 32ll, it->_1._2 % (1ll << 32ll), it->_2);
	}*/
	printf("%lld\n", ans);
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 33024
a = []
def outputList(a):
	for i in range(len(a)):
		if i != len(a)-1:
			print("%d"%a[i],end=' ')
		else:
			print("%d"%a[i],end='\n')

n = int(input().strip())
for i in input().split():
	a.append(int(i))
	if len(a)==n:
		break
for i in range(1,len(a)):
	outputList(a)
	key = a[i]
	j = i - 1
	while j >= 0 and a[j] > key:
		a[j+1] = a[j]
		j -= 1
	a[j+1] = key
outputList(a)

Measured memory_bytes: 8216
using System;

namespace Aizu
{
    class OnlineJudge
    {
        public static void Main()
        {
            var r = double.Parse(Console.ReadLine());
            Console.WriteLine("{0:f6} {1:f6}", r * r * System.Math.PI, r * 2 * System.Math.PI);
        }
    }
}

Measured memory_bytes: 20104
#include <iostream>

using namespace std;
using ll=long long;

int main()
{
    ll n,a,b;cin >>n>>a>>b;
    ll ans;
    if((b-a)%2==0)ans=(b-a)/2;
   else ans= min(a-1,n-b)+1+(b-a-1)/2;
     cout << ans << endl;
    return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<bitset>
#include<set>
#define N (5010)
#define P ()
#define M ()
#define inf (0x7f7f7f7f)
#define rg register int
#define Label puts("NAIVE")
#define spa print(' ')
#define ent print('\n')
#define rand() (((rand())<<(15))^(rand()))
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
typedef long double ld;
typedef long long LL;
typedef unsigned long long ull;
using namespace std;
namespace fastIO1{
	inline char read(){
		static const int IN_LEN=1000000;
		static char buf[IN_LEN],*s,*t;
		return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
	}
	template<class T>
	inline void read(T &x){
		static bool iosig;
		static char c;
		for(iosig=false,c=read();!isdigit(c);c=read()){
			if(c=='-')iosig=true;
			if(c==-1)return;
		}
		for(x=0;isdigit(c);c=read())x=((x+(x<<2))<<1)+(c^'0');
		if(iosig)x=-x;
	}
	inline char readc(char &c){
		for(c=read();!isalpha(c)&&!isdigit(c);c=read())
		if(c==-1)return 0;
	}
	const int OUT_LEN = 10000000;
	char obuf[OUT_LEN],*ooh=obuf;
	inline void print(char c) {
		if(ooh==obuf+OUT_LEN)fwrite(obuf,1,OUT_LEN,stdout),ooh=obuf;
		*ooh++=c;
	}
	template<class T>
	inline void print(T x){
		static int buf[30],cnt;
		if(x==0)print('0');
		else{
			if(x<0)print('-'),x=-x;
			for(cnt=0;x;x/=10)buf[++cnt]=x%10+48;
			while(cnt)print((char)buf[cnt--]);
		}
	}
	inline void flush(){fwrite(obuf,1,ooh-obuf,stdout);}
}
namespace fastIO2{
	template<class T>
	inline void read(T &x){
		static bool iosig;
		static char c;
		for(iosig=false,c=getchar();!isdigit(c);c=getchar()){
			if(c=='-')iosig=true;
			if(c==-1)return;
		}
		for(x=0;isdigit(c);c=getchar())x=((x+(x<<2))<<1)+(c^'0');
		if(iosig)x=-x;
	}
}
using namespace fastIO1;
int n,m,len,mxl,cnt,ot=1; char ch[N],ans[N][N],mn;
void GG(){for(int i=1;i<=n;i++)putchar(mn);exit(0);}
void Min(int &x,int y){
	for(int i=1;i<=n;i++)if(ans[x][i]<ans[y][i])return;
	else if(ans[x][i]>ans[y][i]){x=y;return;}
}
int main(){
	read(n),read(m),mn='z';
	for(int i=1;i<=n;i++)readc(ch[i]),mn=min(mn,ch[i]); if(m>=14)GG();
	for(int i=1;i<=n;i++)if(ch[i]!=mn)len=0;else len++,mxl=max(mxl,len); len=0;
	for(int p=1;p<=n;p++){
		if(ch[p]!=mn)len=0;else len++;
		if(p==n&&len>0){
			int L=len<<m; if(L>=n)GG(); cnt++;
			for(int i=1;i<=L;i++)ans[cnt][i]=mn;
			for(int i=L+1,j=n-len;i<=n;i++,j--)ans[cnt][i]=ch[j];
		}
		else if(len==mxl){
			int L=len<<(m-1); if(L>=n)GG(); cnt++;
			for(int i=1;i<=L;i++)ans[cnt][i]=mn;
			for(int i=L+1,j=p+1;i<=n;i++,j++)ans[cnt][i]=ch[j>n?(2*n-j+1):j];
		}
	}
	for(int i=2;i<=cnt;i++)Min(ot,i); puts(ans[ot]+1);
}

Measured memory_bytes: 12544
#include <bits/stdc++.h>
#define FOR(i,b,e) for (common_type_t <decltype (b), decltype (e)> i = (b), i ## __end = (e); i < i ## __end; ++ i)
#define FORR(i,b,e) for (common_type_t <decltype (b), decltype (e)> i = (e), i ## __begin = (b); i -- > i ## __begin;)
#define rep(i,n) for (decay_t <decltype (n)> i = 0, i ## __len = (n); i < i ## __len; ++ i)
#define ALL(x) begin (x), end (x)
using namespace std;

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

  size_t n, m; cin >> n >> m;
  int64_t c; cin >> c;
  vector <int64_t> b (m);
  rep (i, m) cin >> b[i];
  int64_t ans = 0;
  rep (i, n)
  {
    auto p = c;
    rep (j, m)
    {
      int64_t a; cin >> a;
      p += a * b [j];
    }
    if (p > 0) ++ ans;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int a, b;

int main(){
	scanf("%d %d", &a, &b);
	if (a < b){
		printf("a < b\n");
	} else if (a > b){
		printf("a > b\n");
	} else if (a == b){
		printf("a == b\n");
	};
	return 0;
}


Measured memory_bytes: 2028
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 200_003
R = 2  # primitive root

NTTMOD = 998_244_353
NTT_root = 3
max_ntt = 20


@njit((i8, i8, i8), cache=True)
def mpow(a, n, MOD):
    p = 1
    while n:
        if n & 1:
            p = p * a % MOD
        a = a * a % MOD
        n >>= 1
    return p


@njit((i8, i8), cache=True)
def ntt_precompute(N, primitive_root):
    roots = np.empty(1 << N, np.int64)
    iroots = np.empty(1 << N, np.int64)
    roots[0] = iroots[0] = 1
    for n in range(N):
        x = mpow(primitive_root, (NTTMOD - 1) >> n + 2, NTTMOD)
        y = mpow(x, NTTMOD - 2, NTTMOD)
        for i in range(1 << n):
            roots[(1 << n) | i] = roots[i] * x % NTTMOD
            iroots[(1 << n) | i] = iroots[i] * y % NTTMOD
    return roots, iroots


@njit((i8[:], i8[:], i8[:], numba.b1), cache=True)
def ntt(roots, iroots, A, inverse):
    N = len(A)
    if not inverse:
        m = N >> 1
        while m:
            for k in range(N // m >> 1):
                s = 2 * m * k
                for i in range(s, s + m):
                    x, y = A[i], A[i + m] * roots[k]
                    A[i], A[i + m] = x + y, x - y
            A %= NTTMOD
            m >>= 1
    else:
        m = 1
        while m < N:
            for k in range(N // m >> 1):
                s = 2 * m * k
                for i in range(s, s + m):
                    x, y = A[i], A[i + m]
                    A[i], A[i + m] = x + y, (x - y) * iroots[k]
            A %= NTTMOD
            m <<= 1
        for i in range(N):
            A[i] = A[i] * mpow(N, NTTMOD - 2, NTTMOD) % NTTMOD
    return A


@njit((i8[:], i8[:], i8[:], i8[:]), cache=True)
def ntt_convolve(roots, iroots, A, B):
    A = ntt(roots, iroots, A.copy(), False)
    B = ntt(roots, iroots, B.copy(), False)
    for i in range(len(A)):
        A[i] = A[i] * B[i] % NTTMOD
    ntt(roots, iroots, A, True)
    return A


roots, iroots = ntt_precompute(max_ntt, NTT_root)

@njit((i8[:], ), cache=True)
def precompute(A):
    exp = np.zeros(MOD - 1, np.int64)
    log = np.zeros(MOD, np.int64)
    exp[0] = 1
    for k in range(1, MOD - 1):
        exp[k] = exp[k - 1] * R % MOD
        log[exp[k]] = k
    # r^k の個数を B[k] に入れる
    B = np.zeros(MOD - 1, np.int64)
    for x in A:
        if x != 0:
            B[log[x]] += 1
    return exp, log, B

@njit((i8[:], i8[:], i8[:], i8[:]), cache=True)
def get_ans(A, C, exp, log):
    # 順序対について集計
    ans = 0
    for i in range(len(C)):
        x = exp[i % (MOD - 1)]
        ans += x * C[i]
    for a in A:
        x = a * a % MOD
        ans -= x
    return ans // 2

A = np.array(read().split(), np.int64)[1:]

exp, log, B = precompute(A)

B = np.append(B, [0] * ((1 << 19) - len(B)))
Bh, Bl = B >> 9, B & 511
x = ntt_convolve(roots, iroots, Bh, Bh) << 18
x += ntt_convolve(roots, iroots, Bh, Bl) << 10
x += ntt_convolve(roots, iroots, Bl, Bl)

print(get_ans(A, x, exp, log))

Measured memory_bytes: 154268
// Created by ahmed_drawy on 10/09/19.
///dp educational contest atcoder - vjudge
#include <bits/stdc++.h>
#include <string.h>
#pragma clang diagnostic push
#pragma ide diagnostic ignored "OCUnusedMacroInspection"
using namespace std;
#define lp(i,start , end)       for(int i = start ; i<end ; ++i)
#define lllp(i,start , end)       for(ll i = start ; i<end ; ++i)
#define inN(arr ,  n) for(int i = 0 ; i< n ; ++i)  cin>>arr[i];
#define Rlp(i,start , end)      for(int i = start ; i>end ; --i)
#define all(v)                   ((v).begin(),(v).end())
#define sz(v)                  (int)((v).size())
#define clr(v,d)                memset(v , d , sizeof(v))
#define inf 0x3f3f3f3f
//#define dbg (v)    for(auto it : v)cout<<it<<' ';
typedef long long               ll;
typedef vector<int>             vi;
typedef vector  <ll>            vll;
typedef vector<vector<int> >    adj;
typedef pair<int ,int>          pii;
const double EPS =1e-7;
const int OO = 1e6;
#define endl '\n'
#define cint(c) (int)c -'0';
#define itc(c) (char)c +'A';
bool sortpair( const pair<int , int> & x, const pair<int , int> & y){
    return  x.first != y.first ? x.first < y.first : x.second > y.second ;
}
int dcomp(double x , double y){
    return fabs(x-y) <= EPS? 0: x>y?1:-1;
}

void smile() {
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#ifndef ONLINE_JUDGE
    //freopen("/home/tw3/Desktop/Desktop/training/in.txt", "r", stdin);
//    freopen("/home/tw3/Desktop/Desktop/training/out.txt" , "w" , stdout);
#endif
}
#define fastin smile()

int n ;
const int N = 1e5 +3;
ll dp[N];
int h[N];
int main() {
    fastin;
    int k;
    cin >> n >> k;
    inN(h, n);
    for (int l = 0; l < n; ++l) {
        dp[l] = inf;
    }
    dp[0] = 0;
    for (int j = 1; j < n; ++j) {

        for (int i = j - 1, m = 0; i >= 0 && m < k; m++, --i) {
            dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]));
        }

    }
    cout << dp[n - 1];
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = (int)(n); i >= 0; i--)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

ll N, K, T, W, H, M, C;

const int MAX = 5100000;
const ll MOD = 1e9 + 7;

const double PI=3.14159265358979323846;


long long fac[MAX], finv[MAX], inv[MAX];

vector<double> cx, cy, c;
 ll MM = 1e12;

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll modinv(ll a) {
    ll b = MOD, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= MOD;
    if (u < 0) u += MOD;
    return u;
}

ll modpow(ll x, ll n) {
  ll ret = 1;
  while(n > 0) {
    if(n & 1) (ret *= x) %= MOD;
    (x *= x) %= MOD;
    n >>= 1;
  }
  return ret;
}

struct Eratos {
    vector<int> primes;
    vector<bool> isprime;
    vector<int> min_factor;

    Eratos(int MAX) : primes(),
                      isprime(MAX+1, true),
                      min_factor(MAX+1, -1) {
        isprime[0] = isprime[1] = false;
        min_factor[0] = 0, min_factor[1] = 1;
        for (int i = 2; i <= MAX; ++i) {
            if (!isprime[i]) continue;
            primes.push_back(i);
            min_factor[i] = i;
            for (int j = i*2; j <= MAX; j += i) {
                isprime[j] = false;
                if (min_factor[j] == -1) min_factor[j] = i;
            }
        }
    }

    // prime factorization
    vector<pair<int,int>> prime_factorize(int n) {
        vector<pair<int,int> > res;
        while (n != 1) {
            int prime = min_factor[n];
            int exp = 0;
            while (min_factor[n] == prime) {
                ++exp;
                n /= prime;
            }
            res.push_back(make_pair(prime, exp));
        }
        return res;
    }
};

ll gcd(ll a, ll b) {
  if(a < b) return gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

ll lcm(ll a, ll b)
{
   return a * b / gcd(a, b);
}

  
int main(){
    ll ans = 0;
    cin >> N;
    map<ll, ll> sub, sum;
    ll a;
    for(int i = 1; i < N+1; ++i){
        cin >> a;
        if(i >= a) sub[i-a] += 1;
        sum[a+i] +=1;
    }
    for (auto ent: sub){
        ans += ent.second * sum[ent.first];
    }

    cout << ans;
    return 0;
}


Measured memory_bytes: 22620
#include <bits/stdc++.h>
using namespace std;
#define fastIO                        \
	ios_base::sync_with_stdio(false); \
	cin.tie(NULL);                    \
	cout.tie(NULL);
// g++ -std=c++11 -O2 -Wall *.cpp -o *
#define eps 1e-9
#define MAX 10000001
#define MOD 998244353
#define PI 3.14159265358979323846
#define Fi first
#define Se second
#define PB push_back
#define MP make_pair
#define all(a) a.begin(), a.end()
typedef long long ll;
typedef pair<int, int> pr_int;



int main()
{
	int a, b, x;
	scanf("%d %d %d", &a, &b, &x);
	double res;
	if (2 * x <= a * a * b)
		res = atan(a * b * b * 1.0 / (2 * x));
	else
		res = atan(2.0 * (a * a * b - x) / (a * a * a));
	printf("%.8lf", res * 180 / PI);
	return 0;
}


Measured memory_bytes: 256