akhauriyash/Code-Regression huggingface dataset:
import java.util.* ;
public class Main{
       public static void main( String args[] ){
             Scanner cin = new Scanner( System.in ) ;
             int h = cin.nextInt() ;
             int w = cin.nextInt() ;
             int a[][] = new int[510][510] ;
             for( int i = 1 ; i <= h ; i++ )
                 for( int j = 1 ; j <= w ; j++ )
                     a[i][j] = cin.nextInt() ;
             int cnt = 0 ;
             int x1[] = new int[250010] ;
             int y1[] = new int[250010] ;
             int x2[] = new int[250010] ;
             int y2[] = new int[250010] ;
             for( int i = 1 ; i <= h ; i++ )
                 for( int j = 1 ; j <= w ; j++ ){
                     if ( j < w ){
                         if ( a[i][j] % 2 == 1 ){
                             cnt++ ; 
                             x1[cnt] = i ; y1[cnt] = j ;
                             a[i][j]-- ;
                             a[i][j + 1]++ ;
                             x2[cnt] = i ; y2[cnt] = j + 1 ;
                         }
                     }
                     else{
                         if ( i != h ){
                             if ( a[i][j]  % 2 == 1 ){
                                 cnt++ ;
                                 x1[cnt] = i ; y1[cnt] = j ;
                                 a[i][j]-- ;
                                 a[i + 1][j]++ ;
                                 x2[cnt] = i + 1 ; y2[cnt] = j ;
                             }
                         }
                     }
                 }
            System.out.println( cnt ) ;
            for( int i = 1 ; i <= cnt ; i++ )
                System.out.println( x1[i] + " " + y1[i] + " " + x2[i] + " " + y2[i] ) ;
       }
} 

Measured memory_bytes: 112620
import sys
import math
S = input()

ans_lis = [0] * len(S)

start = 0
end = len(S) - 1

if S[0] == 'L':
    i = 1
    ans_lis[0] = 1
    while S[i] == 'L':
        ans_lis[0] += 1
        i += 1
        if i == len(S):
            print(*ans_lis)
            sys.exit()
    start = i

if S[len(S) - 1] == 'R':
    i = len(S) - 2
    ans_lis[len(S) - 1] = 1
    while S[i] == 'R':
        ans_lis[len(S) - 1] += 1
        i -= 1
        if i == 0:
            print(*ans_lis)
            sys.exit()
    end = i + 1

S += 'T'
right = 0
left = 0
first_left = True
n = start
while n <= end:
    if S[n] == 'R':
        right += 1
        if S[n + 1] == 'L':
            #print('right >>', right)
            ans_lis[n + 1] += math.floor(right / 2)
            ans_lis[n] += math.ceil(right / 2)
            right = 0
        n += 1
    elif S[n] == 'L':
        if first_left:
            first_left = False
            tmp = n
        left += 1
        if S[n + 1] == 'R' or n == end:
            #print('left >>', left)
            ans_lis[tmp - 1] += math.floor(left / 2)
            ans_lis[tmp] += math.ceil(left / 2)
            left = 0
            first_left = True
        n += 1
    #print(ans_lis)
#print('left >>', left)
#print('right >>', right)
print(*ans_lis)

Measured memory_bytes: 6512
n = int(input())
trv = [[0,0,0]]
for i in range(n):
    t,x,y = map(int,input().split())
    a = [t,x,y]
    trv.append(a)

flag = 1

for i in range(1,len(trv)):
    time = trv[i][0]-trv[i-1][0]
    dist = abs(trv[i][1]-trv[i-1][1]) + abs(trv[i][2]-trv[i-1][2])
    if time < dist:
        flag = 0
    elif time >= dist and (time-dist) % 2 == 0:
        None
    else:
        flag = 0
        break
        
if flag == 0:
    print('No')
else:
    print('Yes')

Measured memory_bytes: 19572
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 10000000000000
#define MOD 1000000007
#define mod 1000000007
#define REP(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define REPE(i, a, n) for (ll i = a; i <= (ll)(n); i++)
#define rep(i,n)for(ll i=0;i<(n);i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef pair<int,int>Pin;
typedef pair<ll,ll>Pll;
template<class T> using V=vector<T>;
long long GCD(long long a, long long b) {return b?GCD(b,a%b):a;}
long long LCM(long long a, long long b) {return a/GCD(a,b)*b;}
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int ddx[8]={-1,0,1,0,1,1,-1,-1};
int ddy[8]={0,-1,0,1,1,-1,1,-1};
ll cmp(pair<ll,ll>a,pair<ll,ll> b){
        if(a.se!=b.se)
        return a.se<b.se;
        else
        return a.fi<b.fi;
}
//----------------------------------------------------------------------

//----------------------------------------------------------------------
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------  
    //ll begin_time=clock();
    //-------------------------------
    ll n,q;cin>>n>>q;
    stack<ll>a[1010];
    while(q--){
        int c;cin>>c;
        if(c==0){
            ll t,x;cin>>t>>x;
            a[t].push(x);
        }
        else if(c==1){
            ll t;cin>>t;
            if(a[t].size())
            cout<<a[t].top()<<endl;;
        }
        else{
            ll t;cin>>t;
            if(a[t].size())
            a[t].pop();
        }
    }
    //-------------------------------  
    //ll end_time=clock();cout<<"time="<<end_time-begin_time<<"ms"<<endl;
    //-------------------------------
    return 0;
}
//----------------------------------------------------------------------













































Measured memory_bytes: 4940
import java.util.Scanner;
import java.util.TreeSet;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		if (s.length() == 26) {
			TreeSet<Character> set = new TreeSet<>();
			set.add(s.charAt(25));
			for (int i = 24; 0 <= i; i--) {
				if (set.higher(s.charAt(i)) != null) {
					System.out.println(s.substring(0, i) + set.higher(s.charAt(i)));
					return;
				} else {
					set.add(s.charAt(i));
				}
			}
			System.out.println(-1);
		} else {
			for (int i = 'a'; i <= 'z'; i++) {
				if (s.indexOf(i) == -1) {
					System.out.println(s + (char)i);
					break;
				}
			}
		}
	}
}


Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
map <int,int> mp;
int main()
{
	int n,a,it;
	cin >>n;
	for (int i=0;i<n;i++)
	{
		cin >>a;
		mp[a]++;
	}
	for (map <int, int>::iterator it = mp.begin(); it != mp.end(); it++)
	{
		if (it->second>1)
		{
			cout <<"NO"<<endl;
			return 0;
		}
	}
	cout <<"YES"<<endl;
	return 0;
}

Measured memory_bytes: 9600
#include <iostream>
#include <algorithm>
using namespace std;
static const int MAX=200000;

int main(){
  int n,num_list[MAX];
  cin >> n;
  for(int i=0;i<n;i++) cin >> num_list[i];
  int maxv,minv;
  maxv=num_list[1]-num_list[0];
  minv=num_list[0];
  for(int i=1;i<n;i++){
    maxv=max(maxv,num_list[i]-minv);
    minv=min(minv,num_list[i]);
  }

  cout << maxv << endl;
  return 0;
}

Measured memory_bytes: 1940
#include <iostream>
#include <vector>
#include <map>
#include <math.h>
#include <algorithm>
#include <sstream>
#include <list>

using namespace std;

int main()
{
	long long a[5], n;
	long long i;

	cin >> n >> a[0] >> a[1] >> a[2] >> a[3] >> a[4];

	long long min, res, T, temp;
	min = a[0];
	
	//	point 3
	if (a[0] <= a[1])
		T = n / a[0] + (n % a[0] > 0 ? 1 : 0) + 1;
	else
		T = n / a[1] + (n % a[1] > 0 ? 1 : 0) + 1;
	
	for (i = 2; i < 5; i++)
	{
		min = min > a[i - 1] ? a[i - 1] : min;

		if (min <= a[i])
			T++;
		else
			T = n / a[i] + (n % a[i] > 0 ? 1 : 0) + i;
		
	}

	printf("%lld", T);

	return 0;
}


Measured memory_bytes: 256
def f(n):
    a = []
    for i in range(1,n+1):
        if n%i == 0:
            a.append(i)
    return a

n = int(input())
count = 0
for i in range(1,n+1,2):
    ff = f(i)
    #print(ff)
    if len(ff) == 8:
        count+=1
print(count)


Measured memory_bytes: 2940
/*
AC記録用
自分のコードは実行時間約1分
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3552784#1
*/

#include<iostream>
#include<cstring>
#include<map>
#include<queue>
using namespace std;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int w,h,sx,sy,gx,gy,ans,HM;
int mas[22][22];
bool used[22][22];
typedef pair<int,int> P;
void bfs(int cnt,P p);
P move(P,int);
int main(){
  while(1){
    cin >> w >> h;
    if(w==0&&h==0)break;
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
    cin >> mas[i][j];
    if(mas[i][j]==2)sx=i,sy=j;
      }
    }
    ans=11;
    mas[sx][sy]=0;
    bfs(1,P(sx,sy));
    if(ans>=11)cout << -1 << endl;
    else cout << ans << endl;
  }
}
void bfs(int cnt,P p){
  if(cnt >= ans)return;
  for(int i=0;i<4;i++){
    int nx=p.first+dx[i],ny=p.second+dy[i];
    if((!(nx>=0&&nx<h&&ny>=0&&ny<w))||mas[nx][ny]==1)continue;
    HM=0;
    P p1 = move(P(nx,ny),i);
    if(HM==1)continue;
    nx=p1.first; ny=p1.second;
    if(mas[nx][ny]==3){
      ans = cnt;
      return;
    }
    if(mas[nx][ny]==1){
      mas[nx][ny]--;
      bfs(cnt+1,P(nx-dx[i],ny-dy[i]));
      mas[nx][ny]++;
    }
  }
  return;
}
P move(P p,int i){
  while(1){
    if(!(p.first>=0&&p.first<h&&p.second>=0&&p.second<w)){
      HM=1;
      return p;
    }
    if(mas[p.first][p.second]!=0)return p;
    p.first+=dx[i];
    p.second+=dy[i];
  }
}


Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tairyoku = sc.nextInt();
		int syurui = sc.nextInt();
		int total = 0;
		for(int i= 0; i<syurui;  i++) {
			total  = total + sc.nextInt();
		}
		
		if(total<tairyoku) {
			System.out.println("No");
		}else {
			System.out.println("Yes");
		}

	}

}

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


typedef long long ll;
typedef unsigned long long ull;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define MAX 9223372036854775807
#define MOD 1000000007

int main(void){
    int a[3][3];
    bool ans[3][3];
    rep(i,3){
        rep(j,3){
            cin >> a[i][j];
            ans[i][j]=false;
        }
    }
    int n;
    cin >> n;
    int b[n];
    rep(i, n) cin >> b[i];

   
    rep(i,3){
        rep(j,3){
            rep(k, n){
                if (b[k] == a[i][j])
                    ans[i][j] = true;
            }
        }
    }
    //横
    rep(i,3){
        int cnt = 0;
        rep(j, 3){
            if(ans[i][j])
                cnt++;
        }
        if(cnt ==3){
            cout << "Yes" << endl;
            return 0;
        }
    }
    //たて
    rep(i, 3){
        int cnt = 0;
        rep(j, 3){
            if (ans[j][i])
                cnt++;
        }
        if (cnt == 3){
            cout << "Yes" << endl;
            return 0;
        }
    }
    if(ans[1][1]){
        if(ans[0][0]){
            if(ans[2][2]){
                cout << "Yes" << endl;
                return 0;
            }
        }
        else if(ans[0][2]){
            if(ans[2][0]){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }

    cout << "No" << endl;
    



    return 0;
}


Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
int main() {
	string S, T;
	cin >> S >> T;
	int ans = 0;
	for (int i = 0; i < 3; i++)
		if (S[i] == T[i]) ans++;
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
using P = pair<int,int>;
//#########################################
signed main(){
    int n,m;cin >> n >> m;
    int a[n],b[n];
    vector<P> res;
    rep(i,n){
        cin >> a[i] >> b[i];
        res.emplace_back(a[i],i);
    }
    sort(res.begin(),res.end());
    
    priority_queue<int> pq;
    int ans = 0;
    //rep(i,n)trace(res[i]);

    int i = 0;
    for(int day = 1;day <= m;day++){
        
        for(;i < n && res[i].first == day;i++){
            pq.push(b[res[i].second]);
        }
        //trace(day,i);
        if(pq.size()){
            ans += pq.top();pq.pop();
        }
        
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int vis[68][68];
string str;
string solve="";
vector<char>ak47;
int main()
{
	int a,b,c,d,e,f,g,h,i,j,k,l=0,p,q,r,s,t;
	string word="AKIHABARA";
	cin>>str;
	t=str.size()-1;
	for(i=0;i<=t;i++)
	{
		ak47.push_back(str[i]);
			}
	 for(i=0;i<=t;i++)
	 {
	 	if(i==0&&ak47[i]!='A')
	 	{
	 		ak47.insert(ak47.begin()+i,'A');
	 		t++;
		 }
		 if(i==4&&ak47[i]!='A')
	 	{
	 		ak47.insert(ak47.begin()+i,'A');
	 		t++;
		 }if(i==6&&ak47[i]!='A')
	 	{
	 		ak47.insert(ak47.begin()+i,'A');
	 		t++;
		 }
		 if(i==8&&ak47[i]!='A')
	 	{
	 		ak47.insert(ak47.begin()+i,'A');
	 		t++;
		 }
	 }
	 if(ak47[t]!='A')
	 {
	 	ak47.insert(ak47.begin()+t+1,'A');
	  	t++;
	 }
	d=word.size()-1;
	if(d!=t)
	{
		cout<<"NO";
	}
	else
	{
		for(i=0;i<=t;i++)
		{
			if(word[i]!=ak47[i])
			{
				cout<<"NO";
				return 0;
			}
		}
		cout<<"YES";
	}
	
	
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
inline void write(int x)
{
    if(x<0)
	{
    	putchar('-');
		x=-x;
	}
    if(x>9)
		write(x/10);
    putchar(x%10+'0');
}
int main()
{
	ios::sync_with_stdio(false);
	int n,x,d,a,s;
	n=read();
	x=read();
	d=read();
	s=n;
	while(n--)
	{
		a=read();
		if(a>=x && a<d) s--;
	}
	write(s);
	puts("");
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char c[3]={'r','g','b'};
main(){
  string w;
  while(cin>>w,w[0]!='0'){
    set<string>a;
    a.insert(w);
    queue<pair<string,int> >q;
    q.push(make_pair(w,0));
    while(!q.empty()){
      pair<string,int>ww=q.front();q.pop();
      string s=ww.first;//cout<<s<<endl;
      int d=ww.second;//cout<<d<<endl;
      int cc=0;
      for(int i=0;i<s.size()-1;i++)if(s[i]!=s[i+1])cc++;
      if(!cc){cout<<d<<endl;goto L;}
      for(int i=0;i<s.size()-1;i++){
        if(s[i]!=s[i+1]){
          int p=0;
          for(int k=0;k<3;k++)
            for(int j=0;j<3;j++)
              if(s[i]==c[k]&&s[i+1]==c[j])p=k+j;
          string t=s;
          if(p==3)t[i+1]=t[i]='r';
          else if(p==2)t[i+1]=t[i]='g';
          else t[i+1]=t[i]='b';
          if(!a.count(t)){//cout<<t<<endl;
            q.push(make_pair(t,d+1));
            a.insert(t);
          }
        }
      }
    }
    cout<<"NA"<<endl;
    L:;
  }
}

Measured memory_bytes: 4468
import java.util.*;

public class Main{
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int a = sc.nextInt();
        int b = sc.nextInt();
        
        int h = 100;
        int w = 100;
        
        final int WHITE = 0;
        final int BLACK = 1;
        
        int[][] grd = new int[h][w];
        
        for(int i=0; i<h/2; i++){
            for(int j=0; j<w; j++){
                grd[i][j] = BLACK;
            }
        }
        
        for(int i=0; i<a-1; i++){
            int y = i*2/w*2;
            int x = i*2%w + y%2%2;
            grd[y][x] = WHITE;
        }
        
        for(int i=0; i<b-1; i++){
            int y = h - i*2/w*2 - 1;
            int x = w - i*2%w - 1 - y%2%2;
            grd[y][x] = BLACK;
        }
        
        System.out.println(h + " " + w);
        
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                System.out.print((grd[i][j]==WHITE)? '.' : '#');
            }
            System.out.println("");
        }
    }
}


Measured memory_bytes: 27348
def calc(n, c, w)
  a, s, g = [], [], []
  (0 .. n - 1).each do |i|
    s[i] = [0] * n
    (i .. n - 1).each do |j|
      s[i][j] = (j > 0 ? s[i][j - 1] : 0) + w[j]
    end
  end
  (0 .. n - 1).each do |i|
    g[i] = [false] * n
    g[i][i] = true
  end
  (1 .. n - 1).each do |k|
    (0 .. n - k - 1).each do |i|
      j = i + k
      g[i][j] = (g[i][j - 1] && s[i][j - 1] <= c[j]) || (g[i + 1][j] && s[i + 1][j] <= c[i])
    end
  end
  a[0] = 1;
  (1 .. n - 1).each do |i|
    a[i] = g[0][i] ? 1 : a[i - 1] + 1
    (0 .. i - 1).each do |j|
      a[i] = [a[i], a[j] + 1].min if g[j + 1][i]
    end
  end
  a[-1]
end
1.times do
  c, w = [], []
  n = gets.to_i
  n.times do |i|
    c[i], w[i] = gets.split.map(&:to_i)
  end
  puts calc(n, c, w)
end

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

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

const int mx=1e6+11;
const double PI = acos(-1);
#define MOD 1000000007


#define nl '\n'
#define pb push_back
#define F first
#define S second
#define I insert
#define mp make_pair

#define sz(x) x.size()
#define tt int t; cin>>t; while(t--)
#define lo(i,a,b) for(int i=a;i<b;i++)
#define be(a) (a).begin(),(a).end()
#define rbe(a) (a).rbegin(),(a).rend()
#define mem(a,b) memset(a,b,sizeof(a))

#define su ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define frac cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);

#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
void faltu () {            cerr << endl;}
template < typename T, typename ... hello>void faltu( T arg, const hello &... rest) {cerr << arg << ' ';faltu(rest...);}


int main()
{
   su;
   int n,m,c,a,sum,cnt=0;
   cin>>n>>m>>c;
   int b[m];
   lo(i,0,m)
   {
     cin>>b[i];
   }
   lo(i,0,n)
   {
     sum=c;
     lo(j,0,m)
     {
       cin>>a;
       sum+=(a*b[j]);
     }
     if(sum>0)
      cnt++;
   }
   cout<<cnt<<nl;
   return 0;
}

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


int main() {
  long long n; cin >> n;
  string s; cin >> s;
  
  if(n % 2 == 1){
    cout << "No" << endl;
  }
  else{
    for(int i=0; i < n/2; i++){
      if(s.at(i) != s.at(n/2 + i)){
        cout << "No" << endl;
        break;
      }
      if(i== n/2-1){
        cout << "Yes" << endl;
      }
    }
  }
}
      
    

Measured memory_bytes: 256
#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 210
#define M 100010
#define P 1000000007 
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
int n,m,a[N],f[N][M],fac[N],inv[N];
signed main()
{
	n=read(),m=read();
	for (int i=1;i<=n;i++) a[i]=read();
	sort(a+1,a+n+1);reverse(a+1,a+n+1);
	fac[0]=1;for (int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%P;
	inv[0]=inv[1]=1;for (int i=2;i<=n;i++) inv[i]=P-1ll*(P/i)*inv[P%i]%P;
	f[0][m]=1;
	for (int i=1;i<=n;i++)
	{
		for (int j=0;j<=m;j++)
		{
			f[i][j]=(f[i][j]+1ll*f[i-1][j]*(P+1-inv[n-i+1]))%P;
			f[i][j%a[i]]=(f[i][j%a[i]]+1ll*f[i-1][j]*inv[n-i+1])%P;
		}
	}
	int ans=0;
	for (int j=0;j<=m;j++) ans=(ans+1ll*f[n][j]*fac[n]%P*(j%a[n]))%P;
	cout<<ans;
	return 0;
	//NOTICE LONG LONG!!!!!
}

Measured memory_bytes: 79744
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int x = sc.nextInt();
		int num = 0;
		for (int i = 0; i <= a; i++) {
			for (int j = 0; j <= b; j++) {
				for (int k = 0; k <= c; k++) {
					int y = i * 500 + j * 100 + k * 50;
					if (y == x) {
						num++;
					}
				}
			}
		}
		System.out.println(num);
		sc.close();
	}

}


Measured memory_bytes: 21844
#include <iostream>
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>

using namespace std;

typedef long long LL;

#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 
#define rep(i,n) for (int i = 0; i < (n); ++i)

const int MOD = 1000000007;

bool check(const vector<vector<int>>& e, const vector<int>& cycle) 
{
    // cout << "check is called with " << endl;
    // cout << '\t'; dump(cycle);
    bool ok = true;
    set<int> s;
    rep(i, cycle.size()) s.insert(cycle[i]);
    for (int i = 0; ok && i < cycle.size(); ++i) {
        int count = 0;
        for (int x: e[cycle[i]]) {
            if (s.find(x) != s.end()) {
                ++count;
                if (1 < count) {
                    break;
                }
            }
        }
        ok = (count == 1);
    }
    return ok;
}

int main()
{
    int N, M;
    cin >> N >> M;
    vector<vector<int>> e(N);

    rep(i, M) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        e[a].push_back(b);
    }

    rep(s, N) {
        vector<bool> visited(N);
        queue<vector<int>> q;
        q.push(vector<int>(1, s));
        visited[s] = true;
        int minLen = N+1;
        while (!q.empty()) {
            vector<int> curr = q.front(); 
            q.pop();
            // cout << "curr = "; dump(curr);
            for (int next: e[curr.back()]) {
                // cout << "next = " << next << endl;
                if (next == s) {
                    //! came back to the start point
                    if (check(e, curr)) {
                        //! found the answer
                        cout << curr.size() << endl;
                        rep(x, curr.size()) cout << (curr[x]+1) << endl;
                        return 0;
                    } else {
                        if (minLen < curr.size()) {
                            q = queue<vector<int>>(); //! go to the next s
                            break;
                        } else {
                            minLen = curr.size();
                        }
                    }
                } else if (!visited[next]) {
                    visited[next] = true;
                    vector<int> currPlus = curr;
                    currPlus.push_back(next);
                    q.push(currPlus);
                }
            }
        }
    }

    cout << -1 << endl;

    return 0;
}


Measured memory_bytes: 384
#入力
r, D, x0 = list(map(int,input().split()))
#数列xのリストを作っておく
x = [None for _ in range(10)]
#数列xの初項をリスト中に加えておく
x.insert(0,x0)
#与えられた数列に従い代入する, 結果
for i in range(1,11):
  x[i] = r * x[i-1] - D
  print(x[i])


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

static const int MAX = 100;
static const int INFTY = (1<<21);
static const int white =0;
static const int gray = 1;
static const int black = 2;

int n, M[MAX][MAX];

int dijkstra() {
  int u, minv;
  int d[MAX], color[MAX];

  REP(i, n) {
    d[i] = INFTY;
    color[i] = white;
  }

  d[0] = 0;
  color[0] = gray;

  while( 1 ) {
    minv = INFTY;
    u = -1;
    REP(i, n) {
      if (minv > d[i] && color[i] != black ) {
        u = i;
        minv = d[i];
      }
    }
    if (u == -1) break;
    color[u] = black;
    REP(v, n) {
      if (color[v] != black && M[u][v] != INFTY) {
        if (d[v] > d[u] + M[u][v]) {
          d[v] = d[u] + M[u][v];
          color[v] = gray;
        }
      }
    }
  }
  REP(i, n) {
    cout << i << " " << (d[i] == INFTY ? -1 : d[i]) << endl;
  }
}

int main() {
  cin >> n;
  REP(i, n) {
    REP(j, n) {
      M[i][j] = INFTY;
    }
  }

  int k, c, u, v;
  REP(i, n) {
    cin >> u >> k;
    REP(j, k) {
      cin >> v >> c;
      M[u][v] = c;
    }
  }
  dijkstra();
  return 0;
}

Measured memory_bytes: 3056
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

s = list(input().rstrip())
g = 0
p = 0
res = []
ans = 0

for i in range(len(s)):
    c = g-p
    if s[i] == "g":
        if c > 0:
            #print("p")
            p += 1
            ans += 1
        else:
            #print("g")
            g += 1
    else:
        if c > 0:
            #print("p")
            p += 1
        else:
            #print("g")
            g += 1
            ans -= 1
print(ans)

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

const int maxn = 2e6;
int n, m, K, a[maxn + 3], b[maxn + 3], top, A[maxn + 3], B[maxn + 3];
char s[maxn + 3], t[maxn + 3];

struct node {
	int k, v;
	node(int a = 0, int b = 0) {
		k = a, v = b;
	}
} st[maxn + 3], tmp[maxn + 3];

int main() {
	scanf("%d %d %d %s %s", &n, &m, &K, s + 1, t + 1);
	reverse(s + 1, s + n + 1);
	reverse(t + 1, t + m + 1);
	for (int i = 1; i <= n; i++) {
		a[i] = s[i] ^ '0';
	}
	for (int i = 1; i <= m; i++) {
		b[i] = t[i] ^ '0';
	}
	for (int i = max(n, m); i; i--) {
		if (a[i] && b[i]) {
			int pos = i, lft = K, cur = 3, cnt = 0;
			while (top) {
				if (cur == 3) {
					if (lft >= st[top].k - pos) {
						lft -= st[top].k - pos, pos = st[top].k;
						tmp[++cnt] = st[top], tmp[cnt].v ^= 3;
						cur &= st[top].v;
					} else {
						break;
					}
				} else if (cur) {
					if (st[top].k == pos + 1) {
						pos++;
						if (st[top].v != cur) {
							cur = 3;
						}
					} else {
						break;
					}
				} else {
					break;
				}
				top--;
			}
			if (cur == 3) {
				A[pos + lft] = 1, B[pos + lft] = 1;
			} else if (cur) {
				st[++top] = node(pos + 1, cur);
			}
			for (int i = cnt; i; i--) {
				st[++top] = tmp[i];
			}
		} else if (a[i] || b[i]) {
			st[++top] = node(i, a[i] << 1 | b[i]);
		}
	}
	for (int i = 1; i <= top; i++) {
		A[st[i].k] = st[i].v >> 1;
		B[st[i].k] = st[i].v & 1;
	}
	int N = max(n, m) + K, M = N;
	while (N && !A[N]) N--;
	while (M && !B[M]) M--;
	reverse(A + 1, A + N + 1);
	reverse(B + 1, B + M + 1);
	for (int i = 1; i <= N; i++) {
		putchar(A[i] ^ '0');
	}
	puts("");
	for (int i = 1; i <= M; i++) {
		putchar(B[i] ^ '0');
	}
	puts("");
	return 0;
}

Measured memory_bytes: 65664
#include <stdio.h>
#define N 100
int a[N];
int main(void){
    int i,n;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(i=n-1;i>=0;i--){
        printf("%d",a[i]);
        if(i>0) printf(" ");
    }
    printf("\n");
    return 0;
}


Measured memory_bytes: 2756
a,b,c=map(int,input().split())
if a&1 or b&1 or c&1:
	print("0")
elif a==b and b==c:
	print("-1")
else:
	k=1
	while a%(1<<k)==b%(1<<k) and b%(1<<k)==c%(1<<k):
		k+=1
	print(k-1)

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

int sell[10];
int main() {
  int n,p;
  while(cin>>n, n) {
    for(int i=0; i<10; ++i) sell[i] = 0;
    for(int i=0; i<n; ++i) {
      cin>>p;
      sell[p]++;
    }
    for(int i=0; i<10; ++i) {
      if(sell[i] == 0) cout<<"-";
      else while(sell[i]--) cout<<"*";
      cout<<endl;
    }
  }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
using pint = pair<int,int>;

const long long INFLL = 1LL << 60;
const int INFI = 1000000000;


int main(){
    string S,T; cin >> S >> T;
    int len = S.size();
    string ans = "No";
    for(int i=1;i<len;i++){
        string s = S.substr(len-i,i) + S.substr(0,len-i);
        if(s == T) ans = "Yes";
    }
    if(S == T) ans = "Yes";
    cout << ans << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1001001001;
const ll LINF = 1001001001001001;
const int MOD = 1000000007;

template <typename T>
void print(const T &v);

int main()
{
    int n, W;
    cin >> n >> W;
    vector<int> w(n), v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> w[i] >> v[i];
    }
    vector<ll> dp(W + 1, 0);
    for (int i = 0; i < n; i++)
    {
        for (int j = W; j >= 0; j--)
        {
            if (j >= w[i])
            {
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
    }
    cout << dp[W] << endl;
    return 0;
}

// Use For Debug
template <typename T>
void print(T const &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << ' ';
        cout << v[i];
    }
    cout << endl;
}

Measured memory_bytes: 4052
#include <iostream>

using namespace std;
using ll = long long;

ll S(ll n)
{
    ll s = 0;
    while (n > 0)
    {
        s += n % 10;
        n /= 10;
    }
    return s;
}

int main()
{
    ll K;
    cin >> K;
    ll x = 1, d = 1;
    cout << 1 << endl;
    for (ll i = 1; i < K; ++i)
    {
        /*
         * 例１
         * x = 19999 (現在わかっているすぬけ数)
         * n = 19999 + 1000  = 20999 (次のすぬけ数候補)
         * c = 19999 + 10000 = 29999（次のすぬけ数候補2）
         * 次の数はnかcのどっちかになる
         *
         * 29 * 29999 > 38 * 20999
         * なので次のすぬけ数は 20999
         *
         * 例２
         * x = 39999
         * n = 40999
         * c = 49999
         * 31 * 49999 < 40 * 40999
         *
         * こっちは 49999
         */
        ll n = x + d; //次のインクリメント
        ll c = x + 10 * d; //一つ桁が上のインクリメント
        if(S(n) * c < S(c) * n){ //一つ桁が上のインクリメントのほうが小さかったら
            d *= 10; //桁を上げる
            x = c; //一つ桁が上のインクリメントを採用
        }
        else{
            x = n; //次のインクリメント
        }
        cout << x << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

K = INT()

@lru_cache(maxsize=None)
def memo_gcd(a, b):
	return gcd(a, b)

ans = 0
for i in range(1, K+1):
	for j in range(1, K+1):
		a = gcd(i, j)
		for k in range(1, K+1):
			ans += memo_gcd(a, k)
print(ans)


Measured memory_bytes: 85092
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i < n; i ++)
#define _min(x, y) x = min(x, y)
#define _max(x, y) x = max(x, y)
using namespace std;

const int V = 100005;
vector<int> to[V * 2];
bool visited[V*2];


vector<int> cnt;
void dfs(int v) {
  if (visited[v]) return;
  visited[v] = true;
  cnt[v/V]++;
  for (int u: to[v]) dfs(u);
}

int main() {
  int N;
  int x, y;
  cin >> N;

  rep(i, N) {
    cin >> x >> y;
    y += V;
    to[x].push_back(y);
    to[y].push_back(x);
  }
  long long ans = 0;
  rep(i, V*2) {
    if (visited[i]) continue;
    cnt = vector<int>(2);
    dfs(i);
    ans += (long long)cnt[0] * cnt[1];
  }
  ans -= N;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 10240
#include "bits/stdc++.h"
using namespace std;
const int MAX = 700000;
const int MOD = 1000000007;

long long  fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
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;
}
/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y) {
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}
/*逆元計算*/
long long int  modinv(long long a, long long m) {
	long long int b = m, u = 1, v = 0;
	while (b) {
		long long int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
// index が条件を満たすかどうか
vector<long long int >meguru;
bool isOK(int index, int key) {
	if (meguru[index] > key) return true;
	else return false;
}
// 汎用的な二分探索のテンプレ
int binary_search(int key) {
	int left = -1; 
	int right = (int)meguru.size();
	key = key - 1;
	while (right - left > 1) {
		int mid = left + (right - left) / 2;

		if (isOK(mid, key)) right = mid;
		else left = mid;
	}
	return left;
}
vector<long long int >megurulow;
bool SisOK(int index, int key) {
	if (megurulow[index] > key) return true;
	else return false;
}
// 汎用的な二分探索のテンプレ
int Sbinary_search(int key) {
	int left = -1;
	int right = (int)megurulow.size();
	while (right - left > 1) {
		int mid = left + (right - left) / 2;

		if (SisOK(mid, key)) right = mid;
		else left = mid;
	}
	return right;
}
long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
double PI = 3.141592653589793238;
vector<vector<int>>G(100030);
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	int seen[100030] = {};
	queue<int>q;
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (seen[i] == 0) {
			cnt++;
			q.push(i);
			seen[i] = cnt;		
			while (q.size()) {
				int a = q.front();
				q.pop();
				for (auto iter : G[a]) {
					if (seen[iter] == 0) {
						q.push(iter);
						seen[iter] = seen[a];
					}
				}
			}
		}
	}
	cout << cnt - 1;
}
	

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

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

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

using namespace std;

int main(int qtd, char* nome[])
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    int d[n];
    for(int i = 0; i < n; i++)
        cin >> d[i];
    sort(d, d+n);
    int ans = n%2? 0: abs(d[n/2] - d[n/2-1]);
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
const int MAXN=4+10;
char code[MAXN];
int len;
int main(){
	scanf("%s",&code);
	len=strlen(code);
	for(int i=1;i<len;i++){
		if(code[i]==code[i-1]){
			printf("Bad\n");
			return 0;
		}
	}
	printf("Good\n");
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>

int testcase_ends() {
  size_t n;
  scanf("%zu", &n);
  if (n == 0) return 1;

  std::vector<std::string> s(n);
  for (size_t i=0; i<n; ++i) {
    char buf[256];
    scanf("%s", buf);
    s[i] = buf;
  }

  size_t res=0;
  for (size_t i=0; i<n; ++i) {
    size_t cur=0;
    for (size_t j=0; j<n; ++j) {
      if (s[i][j] == '1') {
        ++cur;
      } else {
        res = std::max(res, cur);
        cur = 0;
      }
    }
    res = std::max(res, cur);
  }

  for (size_t i=0; i<n; ++i) {
    size_t cur=0;
    for (size_t j=0; j<n; ++j) {
      if (s[j][i] == '1') {
        ++cur;
      } else {
        res = std::max(res, cur);
        cur = 0;
      }
    }
    res = std::max(res, cur);
  }

  auto diag=[](const std::vector<std::string> &s)->size_t {
    size_t res=0, n=s.size();
    for (size_t i=0; i<n; ++i) {
      size_t cur=0;
      for (size_t j=0; j<=i; ++j) {
        if (s[j][i-j] == '1') {
          ++cur;
        } else {
          res = std::max(res, cur);
          cur = 0;
        }
      }

      res = std::max(res, cur);
    }
    return res;
  };
  std::vector<std::string> t=s;
  res = std::max(res, diag(s));

  std::reverse(s.begin(), s.end());
  res = std::max(res, diag(s));

  for (auto &si: s) std::reverse(si.begin(), si.end());
  res = std::max(res, diag(s));

  std::reverse(s.begin(), s.end());
  res = std::max(res, diag(s));

  printf("%zu\n", res);
  return 0;
}

int main() {
  while (!testcase_ends()) {}
}



Measured memory_bytes: 2864
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
      	int CONST_MOD = (int) (Math.pow(10, 9) + 7);
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        ArrayList<Integer> dp = new ArrayList<Integer>();
      
      	for(int i=0; i<n+1; i++)
        {
          dp.add(1);
        }
        
        for(int i = 0; i < m; i++)
        {
            dp.set(sc.nextInt(), 0);
        }
        
        for(int i = 2; i < n+1; i++)
        {
            if( dp.get(i) != 0 )
            { 
            	dp.set(i, (dp.get(i-1) + dp.get(i-2))%CONST_MOD);
            }
        }
        
        System.out.println(dp.get(n));
    }
}

Measured memory_bytes: 48004
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
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; }

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> x(n);
    rep(i,n) cin >> x[i];
    int ans = 1e9;
    rep(i,101){
    	int tmp = 0;
    	rep(j,n){
    		tmp += (x[j]-i)*(x[j]-i);
    	}
    	chmin(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
//in the name of god
//if you read this code please search about imam hussain
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb push_back
#define endl "\n";
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define read freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);

const int maxn=1e5+5;
const int mod=1e9+7;
const int inf=1e9;
const int del=728729;
int arr[maxn];
int dp[maxn];
int main(){
	migmig;
	int n;
	cin>>n;
	
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	dp[1]=0;
	dp[2]=abs(arr[2]-arr[1]);
	for(int i=3;i<=n;i++){
		dp[i]=min(dp[i-1]+abs(arr[i]-arr[i-1]),dp[i-2]+abs(arr[i]-arr[i-2]));
	}
	cout<<dp[n];
	return 0;
}



Measured memory_bytes: 1024
#include <cstdio>
#include <algorithm>  
#include <bitset>
#include <cassert>
#include <ctime>  
#include <cmath>  
#include <cstdlib>  
#include <cstring>  
#include <functional>  
#include <iostream>  
#include <deque>  
#include <stack>
#include <queue>  
#include <vector>  
#include <map>  
#include <set>  
#include <string>  
#include <unordered_map>  
#include <unordered_set>  
#pragma warning(disable:4996)

using namespace std;

#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define endl '\n'

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;

const int INF = 1e9;
const int MAXN = 3e3 + 5;
const ll MOD = 998244353;

ll N, S, A[MAXN], ans;
ll D[MAXN][MAXN];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> N >> S;
	for(int i=1; i<=N; i++) cin >> A[i];

	for(int i=1; i<=N; i++) {
		D[i-1][0] = i;
		for(int w=1; w<=S; w++) {
			if(w >= A[i]) D[i][w] = (D[i-1][w] + D[i-1][w-A[i]]) % MOD;
			else D[i][w] = D[i-1][w];
		}
		ans = (ans + D[i][S]) % MOD;
	}
	cout << ans;
}

Measured memory_bytes: 70784
#pragma GCC optimize("Ofast",3,"inline")
#include<bits/stdc++.h>
using namespace std;
#define fir first
#define sec second
#define m_p make_pair
#define y1 ygftgfgcdtfgxffgx
#define y2 yfdsesgvtyghftfvv
#define x1 xvyr6cf6fgcfgf676
#define x2 xcr6rfc5r66y6r6fr
#define up_bound upper_bound
#define low_bound lower_bound
#define next_per next_permutation
#define pb push_back
#define i_to_s to_string
typedef priority_queue<int> p_queue;
typedef priority_queue<int, vector<int>, greater<int> > min_p_queue;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int mon[20]={31,28,31,30,31,30,31,31,30,31,30,31};
ll gcd(ll x,ll y){return ((y==0)?x:gcd(y,x%y));}
ll n,p,ans=1;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n>>p;
	if(n>=60){
		cout<<1;
		return 0;
	}
	if(n==1){
		cout<<p;
		return 0;
	} 
	for(int i=2;i<=p;i++){
		int pos=n;
		ll x=p;
		bool flag=0;
		while(pos--){
			if(x<i){
				cout<<ans;
				return 0;
			}
			if(x%i!=0)flag=1;
			x/=i;
		}
		if(!flag)ans=i;
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
vector <int> v[maxn];
vector <int> p[maxn];
vector <int> top;
int mark[maxn];
int dp[maxn];
int ans;
void dfs(int x) {
	mark[x] = 1;
	for(int i = 0; i < v[x].size(); i++) {
		int u = v[x][i];
		if(mark[u] == 0)
			dfs(u);
	}
	top.push_back(x);
	return;
}
void dfs1(int x) {
	mark[x] = true;
	for(int i = 0; i < p[x].size(); i++) {
		int u = p[x][i];
		if(mark[u] == 0) {
			dp[u] = dp[x];
			dfs1(u);
		}
	}
	return;
}
int main() {
	int n , m;
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int a , b;
		cin >> a >> b;
		v[a].push_back(b);
		p[b].push_back(a);
	}
	for(int i = 0; i < n; i++) {
		if(mark[i] == 0)
			dfs(i);
	}
	reverse(top.begin() , top.end());
	memset(mark , 0 , sizeof mark);
	for(int i = 0; i < n; i++) {
		if(mark[top[i]] == 0) {
			ans++;
			dp[top[i]] = ans;
			dfs1(top[i]);
		}
	}
	int q;
	cin >> q;
	while(q--) {
		int a , b;
		cin >> a >> b;
		if(dp[a] == dp[b])
			cout << 1 << endl;
		else
			cout << 0 << endl;
	}
	return 0;
}



Measured memory_bytes: 9316
#define f(i,a)for(i=0;i<a;i++)
i,j,k,l;s;f;char a[99][55];
main(n,m){
	for(scanf("%d%d\n",&n,&m);gets(a[i++]););
	f(i,n-m+1)f(j,n-m+1){f=1;f(k,m)f(l,m)f&=a[i+k][j+l]==a[n+k][l];s+=f;}
	puts(s?"Yes":"No");
}

Measured memory_bytes: 128
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

// inf
constexpr ll infl = 10000000000000000LL;
constexpr int inf = 1000000000;

int main() {
    int N;
    cin >> N;
    int c4 = 0, co = 0;
    for (int i = 0; i < N; ++i) {
        int a;
        cin >> a;
        if (a % 4 == 0)
            ++c4;
        else if (a % 2 == 1)
            ++co;
    }

    if (co + c4 == N) {
        cout << (co <= c4 + 1 ? "Yes" : "No") << endl;
    } else {
        cout << (co <= c4 ? "Yes" : "No") << endl;
    }
    return 0;
}

Measured memory_bytes: 888
n = int(input())
if n <= 111:
    print(111)
elif n <= 222:
    print(222)
elif n <= 333:
    print(333)
elif n <= 444:
    print(444)
elif n <= 555:
    print(555)
elif n <= 666:
    print(666)
elif n <= 777:
    print(777)
elif n <= 888:
    print(888)
else:
    print(999)

Measured memory_bytes: 3060
#include "bits/stdc++.h"
using namespace std;
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define N           100001
#define rep(i,a,b)  for(int i=a;i<b;i++)
typedef long long ll;

int main() {
        int n;
        cin>>n;
        vector<int> dp(3, 0);
        for(int i = 0; i < n; i++) {
                vector<int> c(3);
                vector<int> new_dp(3, 0);
                for(int &j : c) {
                        cin>>j;
                }
                for(int j = 0; j < 3; j++) {
                        for(int k = 0; k < 3; k++) {
                                if(k != j)
                                new_dp[k] = max(new_dp[k], dp[j] + c[k]);
                        }
                }
                dp = new_dp;
        }
  	cout<<max(dp[0], max(dp[1], dp[2]))<<endl;
}

Measured memory_bytes: 256
# D - Equal Cut
import bisect

N = int(input())
A = list(int(a) for a in input().split())

Acum = [0] * (N+1)
for i in range(N):
    Acum[i+1] = Acum[i] + A[i]

ans = 10**18
for i in range(2, N-1):
    B = bisect.bisect_left(Acum, Acum[i]//2) - 1
    if abs(Acum[B] * 2 - Acum[i]) > abs(Acum[B+1] * 2 - Acum[i]):
        B += 1
    if B == i:
        B -= 1
    elif B == 0:
        B += 1
    P = Acum[B]
    Q = Acum[i] - Acum[B]
    D = bisect.bisect_left(Acum, Acum[i] + (Acum[-1]-Acum[i])//2) - 1
    if abs(Acum[D] * 2 - Acum[i] - Acum[-1]) > abs(Acum[D+1] * 2 - Acum[i] - Acum[-1]):
        D += 1
    if D == N:
        D -= 1
    elif D == i:
        D += 1
    R = Acum[D] - Acum[i]
    S = Acum[-1] - Acum[D]
    mi = min(P, Q, R, S)
    ma = max(P, Q, R, S)
    ans = min(ans, abs(ma - mi))
print(ans)

Measured memory_bytes: 31552
N = int(input())

A = list(map(int, input().split()))

A = sorted(A)
set_A = sorted(list(set(A)))

min_elim = 0
count = 0
sub_count = 0
index = 0

for element in set_A:
    for i in range(index, len(A)):
        if A[i] == element:
            count += 1
        else:
            index = i
            break
    if count > element:
        sub_count = count - element
    elif count < element:
        sub_count = count
    min_elim += sub_count
    count = 0
    sub_count = 0

print(min_elim)


Measured memory_bytes: 15260