akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include<bits/stdc++.h>
#define ll long long
using namespace std;
 
int root(int arr[],int i){
    while(arr[i]!=i){
         arr[i]=arr[arr[i]];
        i=arr[i];
    }
    return i;
}
void Union(int arr[],int Size[],int a,int b){
int rootA=root(arr,a);
int rootB=root(arr,b);
if(Size[rootA]<Size[rootB]){
    arr[rootA]=arr[rootB];
    Size[rootB]+=Size[rootA];
}else{
arr[rootB]=arr[rootA];
Size[rootA]+=Size[rootB];
}
}
bool findRoot(int a,int b,int arr[]){
 if(root(arr,a)==root(arr,b))return true;
 else return false;
}
 vector<vector<int> >adj(105);
bool nCyc=false;
/*void dijkstra(int v,long long dis[]){
dis[v]=0;
multiset<pair<int,int> >s;
s.insert({0,v});
while(!s.empty()){
    pair<int,int>p= *s.begin();
    s.erase(s.begin());
    int x=p.second;
  if(vis[x])continue;
    vis[x]=1;
    for(int i=0;i<adj[x].size();i++){
        int e=adj[x][i].first,w=adj[x][i].second;
      //  cout<<dis[e]<<" "<<dis[x]+w<<endl;
        if(dis[e]>dis[x]+w){
            dis[e]=dis[x]+w;
            s.insert(make_pair(dis[e],e));
        }
    }
}
}*/
/*void bfs(int s){
    queue<int>q;
    q.push(s);
    while(!q.empty()){
        int v=q.front();
        q.pop();
        for(int i=0;i<adj[v].size();i++){
            if(!vis[adj[v][i]]){
                 q.push(adj[v][i]);
                 vis[adj[v][i]]=1;
            }
        }
    }
}*/
int vis[55][55];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
/*bool isVal(int i,int j){
      if(i<0 || j<0 || j>=m || i>=n)return false;
      return true;
}*/
/*void dfs(int i,int j) {
 
    if(!isVal(i,j) || vis[i][j] || arr[i][j]=='#')return;
      vis[i][j]=1;
	  if(arr[i][j]=='G'){
	  check++;
	  }
	  if(arr[i][j]=='B'){
        b=1;
        return;
	  }
	for(int k=0;k<4;k++){
     int pos1=i+dx[k],pos2=j+dy[k];
   //  cout<<pos1<<" "<<pos2<<endl;
     if( isVal(pos1,pos2) && (arr[pos1][pos2]=='#'))continue;
               dfs(pos1,pos2);
	}
}
void dfs2(int i,int j){
 if(isVal(i,j)==false || arr[i][j]!='.')return;
  arr[i][j]='#';
}*/
/*
double prim(int x){
    priority_queue<pair<double,int>,vector<pair<double,int> >,greater<pair<double,int> > >q;
    double min_cost=0.0;
    pair<double,int>p;
     q.push(make_pair(0.0,x));
     while(!q.empty()){
      p=q.top();
      q.pop();
      x=p.second;
      if(vis[x])continue;
      min_cost+=p.first;
      vis[x]=1;
      for(int i=0;i<adj[x].size();i++){
         int y=adj[x][i].second;
         if(!vis[y]){
            q.push(adj[x][i]);
        }
      }
     }
     return min_cost;
}*/
int n;
long long dp[105][100005];
vector<pair<long long ,long long> >v(105);
long long solve(int i,int W){
    if(i==n || W==0)return 0;
    if(dp[i][W]!=-1)return dp[i][W];
    if(v[i].first>W)return solve(i+1,W);
    return dp[i][W]=max(v[i].second+solve(i+1,W-v[i].first),solve(i+1,W));
}
int freq[1000005],check[1000005];
int main()
{
    int W;
    cin>>n>>W;
    for(int i=0;i<n;i++)cin>>v[i].first>>v[i].second;
    memset(dp,-1,sizeof dp);
    cout<<solve(0,W);
return 0;
}

Measured memory_bytes: 85592
import java.util.Scanner;
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 count=0;
        for (int i = a ; i<=b;i++){
            if(c%i==0)count=count+1;
        }
        System.out.println(count);
        sc.close();
    }
    
}


Measured memory_bytes: 26212
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        LinkedList<Integer> deque  = new LinkedList<>();
        for (int i=0;i<n;i++) {
            if (i%2==0) {
                deque.addFirst(sc.nextInt());
            } else {
                deque.addLast(sc.nextInt());
            }
        }

        if (n % 2 == 0) {
            while (!deque.isEmpty()) {
                System.out.print(deque.pollLast() + " ");
            }
        } else {
            while (!deque.isEmpty()) {
                System.out.print(deque.pollFirst() + " ");
            }
        }
    }
}


Measured memory_bytes: 98700
void main() {
	auto ip = readAs!(int[]), A = ip[0], B = ip[1];
	if(A >= 13) writeln(B);
	else if(A <= 5) writeln(0);
	else writeln(B/2);
}
// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}

T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}


Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"

using namespace std;

const long long int MOD = 1000000007;
//const int MOD = 998244353;

long long int N, M, K, H, W, L, R;
//int N, M, K, H, W, L, R;

long long int gcd(long long int a, long long int b) {
	while (b) {
		a %= b;
		swap(a, b);
	}
	return a;
}

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

	cin >> N >> K;
	M = gcd(N, K);
	N /= M;
	cout << (N * 3 - 3)*M << endl;
	return 0;
};

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = (ll)1e9 + 7;
  
int main(){
  int n;
  cin >> n;
  auto d = vector<int>(n,0);
  for (int i = 0; i < n; i++)
  {
      cin >> d[i];
  }

  if(n%2==1){
      cout << 0;
  }else{
      sort(d.begin(),d.end());
      auto i = next(d.begin(),n/2);
      cout << *i - *(i-1);
  }
  
  
}
  

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <map>
#include <cstdlib>
#include <cctype>
#include <ctype.h>
char toupper(char c);
char toupper(char c)
{
    return (c - 0x20);
}

using namespace std;
int main()
{
    int n;
    cin >> n;

        cout << (n - 1) / 2  << endl;
 

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <queue>


using namespace std;

template<class T> inline bool chmin(T& a, T b) {
  //aの方が大きければbに値を更新、そうでなければ何もしない
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
const int INF = 1e9;



int main(){
  int n;
  cin >> n;
  int a[n],b[n],c[n];
  int i;
  for(i=0;i<n;i++){
    cin >> a[i] >> b[i] >> c[i];
  }
  int dpa[n],dpb[n],dpc[n];
  for(i=0;i<n;i++){
    dpa[i]=0;
    dpb[i]=0;
    dpc[i]=0;
  }

  dpa[n-1] = a[n-1];
  dpb[n-1] = b[n-1];
  dpc[n-1] = c[n-1];
  for(i=n-2;i>=0;i--){
    dpa[i] = a[i] + max(dpb[i+1],dpc[i+1]);
    dpb[i] = b[i] + max(dpa[i+1],dpc[i+1]);
    dpc[i] = c[i] + max(dpa[i+1],dpb[i+1]);
  }

  int ans = max(max(dpa[0],dpb[0]),dpc[0]);
  cout  << ans << endl;






}

Measured memory_bytes: 2560
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<map>
#include<cmath>
#define ll long long
#define INF 0x3f3f3f3f
#define maxn 1005
using namespace std;
int read()
{
    int l=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        w=-1;
        else
        ch=getchar();
    }
    while(ch<='9'&&ch>='0')
    {
        l*=10;
        l+=ch-'0';
        ch=getchar();
    }
    return l*w;
}
int a,b,c;
int main()
{
	a=read(),b=read(),c=read();
	if(c<=b)
	printf("%d\n",b+c);
	else
	{
		int ans=0;
		if(a+b<c)
		{
			
			ans=2*b;
			c-=b;
			ans+=a+1;
		}
		else
		{
			ans=b+c;
		}
		printf("%d\n",ans);
	}
	return 0;
}

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

using namespace std;

int wa(int n){
    int count = 0;
    while(1){
        count += n%10;
        n = n /10;
        if(n == 0){
            break;
        }
    }
    return count;
}

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

    int FN = wa(N);

    if(N % FN == 0){
        puts("Yes");
        return 0;
    }else{
        puts("No");
        return 0;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	string str;
	cin>>str;
	int min_diff=INT_MAX;
	int l = 0, r = 2;
	while(r!=str.size())
	{
		int nov = 0;
		int step = 100;
		for(int i = l; i<=r; i++)
		{
			nov+=int(str[i]-'0')*step;
			step/=10;
		}
		min_diff = min(min_diff, abs(753 - nov));
		l++;
		r++;
	}
	cout<<min_diff<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define mo 1000000007
using namespace std;
int n;
int a[5][105];
int f[5][105];
int main(){
	scanf("%d",&n);
	for (int i=1;i<=2;i++)
		for (int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	for (int i=1;i<=2;i++)
		for (int j=1;j<=n;j++)
			f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];
	printf("%d",f[2][n]);
} 


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep0(i,n) for(ll (i) = 0; (i) < (n); ++(i))
#define rrep0(i,n) for(ll (i) = (n) - 1; (i) >= 0; --(i))
#define rep1(i,n) for(ll (i) = 1; (i) <= (n); ++(i))
#define rrep1(i,n) for(ll (i) = (n); (i) >= 1; --(i))
#define nfor(i,a,b) for(ll (i) = (a); (i) < (b); ++(i))
#define rfor(i,a,b) for(ll (i) = (a); (i) > (b); --(i))
#define ll long long
#define mod (1000000007)
#define pf(x) cout << (x) << endl;
#define all(x) (x).begin(),(x).end()

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

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

ll factorial(ll n){
    ll t = 1;
    rep1(i, n)t *= i;
    return t;
}

ll combinations(ll n, ll k) {
    ll r = 1;
    for (ll i = 1; i <= k; ++i) {
        r *= n--;
        r /= i;
    }
    return r;
}

int main()
{
    ll h,w,ans = 0;
    cin >> h >> w;
    vector<vector<ll> > cost(10,vector<ll>(10,0));
    rep0(i, 10)rep0(j, 10){
        ll c;
        cin >> c;
        cost[i][j] = c;
    }
    rep0(k, 10)rep0(i, 10)rep0(j,10)cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
    rep0(i, h)rep0(j, w){
        ll a;
        cin >> a;
        if(a != -1)ans += cost[a][1];
    }
    pf(ans)
    return 0;
}


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

int main() {
  int N,n;
  string S;
  cin >> N;
  cin >> S;
  bool b = false;
  if (N%2 == 1) {
    b = false;
  }
  else {
    n = N/2;
    for (int i = 0;i < n; i++) {
      if (S.at(i) != S.at(i+n)){
        b = false;
        break;
      }
      else {
        b = true;
      }
    }
  }
  if (b == false) {
    cout << "No" << endl;
  }
  if (b == true) {
    cout << "Yes" << endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int N;
string S;
int num[12];int ba;
int main()
{
	while(true){
		scanf("%d",&N);
		if(N==0)return 0;
		cin >> S;
		for(int i=0;i<12;i++){
			num[i]=0;
		}
		ba=0;
		for(int i=0;i<100;i++){
			if(S[i]=='S'){
				ba+=num[i%N]+1;num[i%N]=0;
			}
			else if(S[i]=='L'){
				num[i%N]+=(ba+1);ba=0;
			}
			else{
				num[i%N]++;
			}
		}
		sort(num,num+N);
		for(int i=0;i<N;i++){
			printf("%d ",num[i]);
		}
		printf("%d\n",ba);
	}
	return 0;
}

Measured memory_bytes: 1244
// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input = input.split("\n");
     abk  = input[0].split(" ");
	//文字列から10進数に変換するときはparseIntを使います
	var a = parseInt(abk[0], 10);
    var b = parseInt(abk[1], 10);
    var k = parseInt(abk[2], 10);
   
   if(a<=k){var ak=k-a;
           var  a=0;
          // console.log(ak,b);
            if(b<=ak){var b=0;}
                      else{var b = b-ak;}
            }
            else{var a = a-k;}
            
 console.log(a,b); 
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21192
#include <bits/stdc++.h>
#define INF (1 << 30)
using namespace std;

int A[100000][3];
int dp[100001][3];
int main(){
	int n;
	cin >> n;
	dp[0][0] = dp[0][1] = dp[0][2] = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < 3; j++){
			cin >> A[i][j];
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < 3; j++){
			for(int k = 0; k < 3; k++){
				if(j != k){ // k -> j
					dp[i+1][j] = max(dp[i+1][j], dp[i][k] + A[i][j]);
				}
			}
		}
	}
	cout << max(max(dp[n][0], dp[n][1]), dp[n][2]);
}

Measured memory_bytes: 2560
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N, K = map(int, input().split())
    snk = [0] * (N + 1)
    for _ in [0] * K:
        D = int(input())
        A = map(int, input().split())

        for a in A:
            snk[a] += 1
    print(snk[1:].count(0))


main()


Measured memory_bytes: 9188
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
  ll n,i,ans = 0;scanf("%lld",&n);
  ll a[n+1],b[n];
  for(i=0;i<=n;i++) scanf("%lld",&a[i]);
  for(i=0;i<n;i++) scanf("%lld",&b[i]);
  for(i=0;i<n;i++){
    if(b[i]>=a[i]+a[i+1]){
      ans += a[i]+a[i+1];a[i] = a[i+1] = 0;
    } else if(b[i]>=a[i]){
      ans += b[i];a[i+1] -= b[i]-a[i];a[i] = 0;
    } else{
      ans += b[i];a[i] -= b[i];
    }
  }
  printf("%lld\n",ans);
}

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

typedef pair< int, int > P;

#define MAX_S 12

P MakeNum( const char* );

bool Check[ ( 1 << ( MAX_S * 2 ) ) - 1 ][ MAX_S + 1 ];

int main() {
	char ch[ MAX_S + 1 ];
	int n;  scanf( "%d", &n );
	while( n-- ) {
		scanf( "%s", ch );
		if( ch[ 0 ] == 'i' ) {
			scanf( "%s", ch );
			P p = MakeNum( ch );
			Check[ p.first ][ p.second ] = true;
		} else {
			scanf( "%s", ch );
			P p = MakeNum( ch );
			if( Check[ p.first ][ p.second ] ) printf( "yes\n" );
			else printf( "no\n" );
		}
	}
	return 0;
}

P MakeNum( const char* ch ) {
	int res = 0;
	int i = 0;
	for( ; ch[ i ] != '\0'; ++i ) {
		int num;
		switch( ch[ i ] ) {
		case 'A' : num = 0; break;
		case 'C' : num = 1; break;
		case 'G' : num = 2; break;
		case 'T' : num = 3; break;
		};
		res |= num << ( i * 2 );
	}
	--i;
	return P( res, i );
}

Measured memory_bytes: 15504
// Created by ...
#include <bits/stdc++.h>

#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'

#define vll vector< ll >
#define M 100000
#define MD 1000000007
#define pb push_back
#define rep(i,a,b) for(ll i = a; i <= b; ++i)
#define fo(i,a,b) for(int i = a; i<= b; ++i)
#define pii pair<ll,ll> 
#define vec(a) vector<a >
#define all(a) a.begin(),a.end()
#define se second
#define fi first
#define inf 0xffffffff
#define inchar getchar_unlocked
#define outchar(x) putchar_unlocked(x)
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

using namespace std;
using ll = long long;
ll md=MD;

ll exp(ll a,ll b){ll r=1ll;while(b>0){if(b&1){r=r*(a%md);r=(r+md)%md;}b>>=1;a=(a%md)*(a%md);a=(a+md)%md;}return (r+md)%md;}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll Min(ll a,ll b){if(a<b)return a; return b;}
ll Max(ll a,ll b){if(a>b)return a; return b;}
int32_t main() {
    IOS;

        ll a,b,c;
        cin>>a>>b>>c;
        cout<<c<<" "<<a<<" "<<b;
        



        cout<<'\n';
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#define ll long long
#define oo (ll)1<<62
#define MAX 100005
using namespace std;

int main() {
    static ll n, k, a[MAX], case1, case2, ans = oo;
    cin >> n >> k;
    for (ll i = 0; i < n; ++i) cin >> a[i];
    for (ll i = 0; i <= n-k; ++i) {
        case1 = abs(a[i])       + abs(a[i] - a[i+k-1]); // left to right
        case2 = abs(a[i+k-1])   + abs(a[i] - a[i+k-1]); // right to left
        ans = min(ans, min(case1, case2));
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 1024
N = int(input())
S = list(input())

# print(N, S)
ans = N

f = S[0]
s = S[1:]

nw = 0
ne = 0

for w in s:
    if w != 'W':
        ne += 1

ans = nw+ne
for i in range(1, N):
    # skipflg = False
    # f = S[0: i]
    # l = S[i]
    # s = S[i+1:]
    # # print(i, f, l, s)
    # nw = f.count('W')
    # ne = s.count('E')
    # print(nw, ne)

    if S[i-1] != 'E':
        nw += 1

    if S[i] != 'W':
        ne -= 1
    # print(nw, ne)
    ans = min(ans, nw+ne)

print(ans)


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

int main(){
int N,M;
  cin>>N>>M;
  vector<int>a(M), b(M), count(N);
  for(int i=0; i<N; i++){
   count[i]=0;
  }
  for(int i=0; i<M; i++){
   cin>>a[i]>>b[i];
   count[a[i]-1]++;
   count[b[i]-1]++;
  }
  
  for(int i=0; i<N; i++){
   cout<<count[i]<<endl;
  }
  
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

#define rep(i,n) for(int i=0; i<(n); i++)
#define repc(i,s,e) for(int i=(s); i<(e); i++)
#define pb(n) push_back((n))
#define mp(n,m) make_pair((n),(m))
#define all(r) r.begin(),r.end()
#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;






int main() {
	ll n, s = 0, a;
	cin >> n;
	rep(i, n) {
		cin >> a;
		s += a;
	}
	s /= n;
	cout << s << endl;
}

Measured memory_bytes: 1152
n,m = map(int,input().split())

A = [list(map(int,input().split())) for i in range(n)]


B = [int(input()) for j in range(m)]


for i in range(n):
  sum =0
  for j in range(m):
    sum+= A[i][j]*B[j]
  print(sum)



Measured memory_bytes: 6012
#include <bits/stdc++.h>
using namespace std;
#include <algorithm>
 
int main() {
 
  int long long t=0,i=0,j=0;
  string ans="No",N;
  int long long now=0;

  cin >> N;
  
  for ( i = 0; i < N.size(); i++)
  {
    int a=N[i]-'0';
    now+=a;
    
  }

  if (now%9==0)
  {
    ans="Yes";
  }
  
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 3744
while True:
    n=int(input())
    if n == 0:
        break
    b=[]
    for i in range(n):
        a=int(input())
        b.append(a)
    c=sorted(b)
    if n == 3:
        print(c[1])
    elif n >= 4:
        d=sum(c)-c[0]-c[n-1]
        e=n-2
        print(d//e)


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

typedef long long ll;
typedef vector<int> vi;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)

int main(){
    int a;
    string s;

    cin >> a >> s;

    if(a >= 3200)
        cout << s << endl;
    else
        cout << "red" << endl;

    return 0;
}

Measured memory_bytes: 256
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

int main() {

	//入力
	int N;long long K;cin >> N >> K;
	vector<long long> A(N);
	for (int i = 0; i < N; ++i) cin >> A[i];

	long long res = 0;

	//実装のtips
	//d=-1にしておけばe>dのところで、Kそのものを試せる。

	//Kのビットを上からみて、はじめて一致しない位置をdとして
	//dを全探索する

	//Xは
	//dより上の桁はKと一致
	//d桁目は0
	//dより小さい桁はXは自由にとれる

	//具体例でいうと
	//101001の10"1"001を0にすると1000は0111より大きいので
	//それより小さい桁は1を自由に使える
	
	for (int d = 60; d >= -1; --d) { 

		//d!=-1でないかつ
		//Kより大きい位置桁は無効
		//Kとdが重なるビットがないときははじく
		if (d != -1 && !(K & (1LL << d))) continue;

		//この回の結果を格納する変数
		long long tmp = 0;

		//上で決めたdの状態の各桁eの計算を桁ごとに行う
		for (int e = 60; e >= 0; --e) {

			//bitであることがわかりやすいように名前つけておく
			long long mask = 1LL << e;

			//全ての入力に対して、今注目している桁に何個ビットが立っているか
			//総和を求める 
			int num = 0;
			for (int i = 0; i < N; ++i) if (A[i] & mask) ++num;


			//dより大きい桁では、Kと一致するようにとるしかない
			if (e > d) {

				//X=K=1なら今立ってる1が反転するので(N-num)だし
				if (K & mask) tmp += mask * (N - num);

				//X=K=0なら今立ってる1をそのまま足す
				else tmp += mask * num;
			}

			//d番目の桁は0しかない
			else if (e == d) {
				tmp += mask * num;
			}

			//dより小さい桁は自由に0,1を選べるので
			//両方のうち大きい方をとる
			else {
				tmp += mask * max(num, N - num);
			}
		}

		//一つのdに対しての結果が求まったので、最大値を更新する
		res = max(res, tmp);
	}

	//出力して終了
	cout << res << endl;
}

Measured memory_bytes: 1024
// TOPSIC001_0

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

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

    cout << min(B / A, C);


    return 0;
}

Measured memory_bytes: 256
# encoding: utf-8
import math
N = int(input())
A = list(map(int, input().split()))

def binsearch(seq, l, r, tar):
    # print("##", l, r, LmR[l:r + 1], tar)
    m = l + (r - l) // 2
    if l >= r: return l
    elif seq[m] < tar: return binsearch(seq, m + 1, r, tar)
    else: return binsearch(seq, l, m, tar)

# sum(A[i:j]) == Asum[j] - Asum[i]
Asum = [0]
tmp = 0
for Ai in A:
    tmp += Ai
    Asum.append(tmp)

LmR = []
for SAi in Asum[:-1]:
    LmR.append(-Asum[-1] + 2 * SAi)

b1, b3 = (1, 3)
parts = [A[0], A[1], A[2], Asum[N] - Asum[3]]
ans = max(parts) - min(parts)
for b2 in range(2, N - 1):
    parts[1] -= A[b2]
    parts[2] += A[b2]
    if b3 == b2: b3 = b2 + 1
    # b1
    for btmp in range(b1, b2):
        bfr = math.fabs((Asum[b2] - Asum[btmp]) - (Asum[btmp] - Asum[0]))
        aft = math.fabs((Asum[b2] - Asum[btmp + 1]) - (Asum[btmp + 1] - Asum[0]))
        if aft < bfr: continue
        else: break
    b1 = btmp
    # b3
    for btmp in range(b3, N):
        bfr = math.fabs((Asum[N] - Asum[btmp]) - (Asum[btmp] - Asum[b2]))
        aft = math.fabs((Asum[N] - Asum[btmp + 1]) - (Asum[btmp + 1] - Asum[b2]))
        if aft < bfr: continue
        else: break
    b3 = btmp
    # update
    parts = [Asum[b1], Asum[b2] - Asum[b1], Asum[b3] - Asum[b2], Asum[N] - Asum[b3]]
    if ans > max(parts) - min(parts): ans = max(parts) - min(parts)

print(ans)

# TLE
# # find b2 initial position (sub-optimal)
# tar = 0
# b2 = binsearch(LmR, 2, N - 2, tar)
# if tar - LmR[b2 - 1] < LmR[b2] - tar: b2 = max((2, b2 - 1))
# # b1
# tar = -(Asum[N] - Asum[b2])
# b1 = binsearch(LmR, 1, b2 - 1, tar)
# if tar - LmR[b1 - 1] < LmR[b1] - tar: b1 = max((1, b1 - 1))
# # b3
# tar = Asum[b2]
# b3 = binsearch(LmR, b2 + 1, N - 1, tar)
# if tar - LmR[b3 - 1] < LmR[b3] - tar: b3 = max((b2 + 1, b3 - 1))

# parts = (Asum[b1], Asum[b2] - Asum[b1], Asum[b3] - Asum[b2], Asum[-1] - Asum[b3])
# ans = max(parts) - min(parts)
# b2_init = b2

# # sweep b2
# for b2 in range(2, N - 1):
#     # escape
#     if b2 == b2_init: continue
#     elif LmR[b2] < -2 * ans: continue
#     elif LmR[b2] > 2 * ans: break
#     # b1
#     tar = -(Asum[N] - Asum[b2])
#     b1 = binsearch(LmR, 1, b2 - 1, tar)
#     if tar - LmR[b1 - 1] < LmR[b1] - tar: b1 = max((1, b1 - 1))
#     # escape
#     if math.fabs((Asum[b2] - Asum[b1]) - (Asum[b1])) >= ans: continue
#     # b3
#     tar = Asum[b2]
#     b3 = binsearch(LmR, b2 + 1, N - 1, tar)
#     if tar - LmR[b3 - 1] < LmR[b3] - tar: b3 = max((b2 + 1, b3 - 1))
#     parts = (Asum[b1], Asum[b2] - Asum[b1], Asum[b3] - Asum[b2], Asum[-1] - Asum[b3])
#     if max(parts) - min(parts) < ans: ans = max(parts) - min(parts)
    
# print(ans)

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

int main() {
  ll a, b, c, d;
  cin >> a >> b >> c >> d;
  ll sum1 = b / c - (a - 1) / c;
  ll sum2 = b / d - (a - 1) / d;
  ll lcm = c * d / __gcd(c, d);
  ll sum3 = b / lcm - (a - 1) / lcm;
  cout << (b - a + 1) - (sum1 + sum2 - sum3) << endl;
  return 0;
}


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

int main(){
  int n, m;
  cin >> n >> m;
  int a[m], b[m];
  rep(i, m) cin >> a[i] >> b[i];
  bool can1[n+1], can2[n+1];
  rep(i, n+1) can1[i] = false, can2[i] = false;
  can1[1] = true, can2[1] = true;
  rep(i,m) if(a[i] == 1) can1[b[i]] = true;
  rep(i,m){
    if(can1[a[i]]) can2[b[i]] = true;
    if(can1[b[i]]) can2[a[i]] = true;
  }
  cout << (can2[n]? "POSSIBLE" : "IMPOSSIBLE") << endl;;
  return 0;
}


Measured memory_bytes: 2176
/**
 *    author  : 𝒌𝒚𝒐𝒎𝒖𝒌𝒚𝒐𝒎𝒖𝒑𝒖𝒓𝒊𝒏
 *    created : 2019-12-18 21:39:35
**/

#include <iostream>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
#include <bitset>
#include <cassert>
#include <cctype>
#include <functional>
#include <iomanip>
#include <random>
#include <utility>
#include <chrono>

using namespace std;

using int64 = long long;
template<class T> ostream& operator<<(ostream& os, vector<T>& _) { os << '{'; for (T& x : _) { os << x; if (&x != &_.back()) os << ','; } os << '}'; return os; }
template<class T, class U> ostream& operator<<(ostream& os, pair<T, U>& p) { return os << '{' << p.first << " " << p.second << '}'; }

#ifdef LOCAL
#define debug(_) cerr << #_ << ": " << (_) << '\n'
#else
#define debug(_) 1728
#endif

template <typename T>
class CumulativeSum2D {
 public:
  CumulativeSum2D(const std::vector<vector<T>>& vec)
      : vec_(vec), height_(vec.size()), width_(vec[0].size()) {
    Build();
  }
  // return sum of [sx, gx] * [sy, gy]
  T Get(int sx, int sy, int gx, int gy) {
    assert(sx <= gx && sy <= gy);
    assert(0 <= sx && sx < height_ && 0 <= gx && gx < height_ && 0 <= sy &&
          sy < width_ && 0 <= gy && gy < width_);
    return sum_[gx + 1][gy + 1] - sum_[gx + 1][sy] - sum_[sx][gy + 1] +
          sum_[sx][sy];
  }

 private:
  size_t height_;
  size_t width_;
  std::vector<vector<T>> vec_;
  std::vector<vector<T>> sum_;
  void Build() {
    sum_.assign(height_ + 1, vector<T>(width_ + 1, static_cast<T>(0)));
    for (size_t i = 0; i < height_; ++i) {
      for (size_t j = 0; j < width_; ++j) {
        sum_[i + 1][j + 1] = sum_[i + 1][j] + vec_[i][j];
      }
    }
    for (size_t i = 0; i < width_; ++i) {
      for (size_t j = 0; j < height_; ++j) {
        sum_[j + 1][i + 1] += sum_[j][i + 1];
      }
    }
  }
};

void ABC106_D() {
  int n, m, query; cin >> n >> m >> query;
  vector<vector<int>> board(n, vector<int>(n));
  for (int i = 0; i < m; ++i) {
    int l, r; cin >> l >> r; --l; --r;
    ++board[l][r];
  }

  CumulativeSum2D<int> cs2(board);

  for (int i = 0; i < query; ++i) {
    int p, q; cin >> p >> q;
    --p; --q;
    cout << cs2.Get(p, p, q, q) << '\n';
  }  
}

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

  ABC106_D();

  return 0;
}

Measured memory_bytes: 3968
MOD = 2019

def solve(S):
    N = len(S)
    dp = [0 for _ in range(MOD)]
    tmp = 0
    ret = 0
    for i in range(N - 1, -1, -1):
        m = (tmp + int(S[i]) * pow(10, N - i - 1, MOD)) % MOD
        ret += dp[m]
        dp[m] += 1
        tmp = m
    ret += dp[0]
    return ret

if __name__ == "__main__":
    S = input()
    print(solve(S))

Measured memory_bytes: 68116
import sys
sys.setrecursionlimit(1000000)
n,m = map(int,input().split())
bn = [[int(i) for i in input().split()]+[j] for j in range(m)]
ans = [0]*m
bn.sort()
temp = 0
cnt = 0

for i in bn:
  if temp == i[0]:
    cnt += 1
    ans[i[2]] = '%06d%06d' % (temp,cnt)
  else:
    temp = i[0]
    cnt = 1
    ans[i[2]] = '%06d%06d' % (temp,cnt)   
for j in ans:
  print(j)

Measured memory_bytes: 31296
N, K, C = map(int, input().split())
S = input()

L = [0]*K
R = [0]*K
lpiv = 0
rpiv = N-1
for i in range(K):
    while S[lpiv] == 'x':
        lpiv += 1
    while S[rpiv] == 'x':
        rpiv -= 1
    L[i] = lpiv
    R[i] = rpiv
    lpiv += C+1
    rpiv -= C+1

ans = 0
for i in range(K):
    if L[i]==R[K-i-1]:
        print(L[i]+1)


Measured memory_bytes: 25012
#include <cstdio>

const int mxn = 105;

int n, a[mxn], cnt = 0;

inline void swap(int &x, int &y) {
	int z;
	z = x;
	x = y;
	y = z;
	++cnt;
}

signed main() {
	scanf("%d", &n);
	
	for (int i = 0; i < n; ++i)
		scanf("%d", a + i);
		
	// selection sort
	for (int i = 0; i < n; ++i) {
		int mini = i;
		
		for (int j = i; j < n; ++j)
			if (a[j] < a[mini])
				mini = j;
		
		if (i != mini)
			swap(a[i], a[mini]);
	}
	
	// print array
	for (int i = 0; i < n - 1; ++i)
		printf("%d ", a[i]);
	printf("%d\n", a[n - 1]);
	
	printf("%d\n", cnt);
		
	return 0;
}

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

int main() {
  long N;
  cin >> N;
  long long ans = 0;
  for (long i = 1; i <= N; i++) {
    if (i % 3 != 0 && i % 5 != 0) {
      ans += i;
    }
  }
  cout << ans;
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
#define all(ppp) ppp.begin(),ppp.end()
#define out(ppp) cout<<(ppp)<<endl
#define out1(ppp) cout<<(ppp) 
#define MAX_CHAR 256

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define pb push_back

typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<vpi> vvpi;

typedef set<pi> spi;

const int INF=INT_MAX;
vvi g;
ll K;
ll N;
ll sum=1;
vb visited;
// dfs return dist1;
void dfs(ll curr,ll p,ll dist1,ll dist2){
    sum=sum*(K-dist1-dist2)%MOD;
    for(auto to:g[curr]){
        if(to==p){
            continue;
        }
        dfs(to,curr,1,dist1);
        dist1++;
    }
}





int main(){
    cin>>N>>K;
    g.resize(N+1);
    visited.assign(N+1,0);
    for(ll i=1;i<N;i++){
        ll a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1,-1,0,0);   // currNOde parent dist1 dist2
    out(sum);
    return 0;
}


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

int a[3][3];

int main() {
    for (int i=0; i<3; ++i) for (int j=0; j<3; ++j) cin >> a[i][j];
    int N;
    cin >> N;
    for (int k=0; k<N; ++k) {
        int b;
        cin >> b;
        for (int i=0; i<3; ++i) for (int j=0; j<3; ++j) if (a[i][j] == b) a[i][j] = -1;
    }

    bool bingo = false;
    for (int i=0; i<3; ++i) {
        bool flag = true;
        for (int j=0; j<3; ++j) flag &= (a[i][j] == -1);
        bingo |= flag;

        flag = true;
        for (int j=0; j<3; ++j) flag &= (a[j][i] == -1);
        bingo |= flag;
    }

    bool flag = true;
    for (int i=0; i<3; ++i) flag &= (a[i][i] == -1);
    bingo |= flag;

    flag = true;
    for (int i=0; i<3; ++i) flag &= (a[i][2-i] == -1);
    bingo |= flag;

    puts(bingo ? "Yes" : "No");
}

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

int main(){
    string s;
    cin>>s;
    int n=s.size();
    vector<int> v;
    int count = 0;
    char tmp = 'R';
    for(int i=0; i<n ; i++){
        if(tmp==s.at(i)) count++;
        else{
            tmp=s.at(i);
            v.push_back( count );
            count = 1;
        }
    }
    v.push_back( count );
    int t = 0 ;
    vector< int > ans( n + 1 );
    for(int i=0; i < v.size() ; i += 2){
        int left = v.at(i);
        int right = v.at( i + 1);
        int sum = left + right;
        t += left;
        ans.at( t )= (left%2==1) ? (sum+1)/2 : sum/2;
        if( (right%2)==1 ) ans.at(t+1)=(sum+1)/2;
        else ans.at(t+1)= sum/2;
        t += right;
    }
    for(int i =1; i< n+1 ; i++){
        cout<<ans.at(i)<<" ";
    }
    cout<<endl;
    return 0;
}


Measured memory_bytes: 1528
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pi 3.141592653589793238
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MOD 1000000007
void seive(vector<int> &v,int n)
{
	for(int i=1;i<=n;i++)
		v[i]=i;
	for(int i=2;i<=n;i+=2)
		v[i]=2;
	for(int i=3;i*i<=n;i++)
	{
		if(v[i]==i)
		{
			for(int j=i;j<=n;j+=i)
				if(v[j]==j)
					v[j]=i;
		}
	}
}

int main(){
	fast;
	ll n;
	cin>>n;
	vector<int> v(n+1,1);
	ll arr[n+1]{};
	ll ans=1;
	seive(v,n);
	for(int i=2;i<=n;i++)
	{
		int x=i;
		while(x!=1)
		{
			arr[v[x]]++;
			x=x/v[x];
		}
	}
	for(int i=1;i<=n;i++)
		if(arr[i]>=1)
			ans=(ans*(arr[i]+1))%MOD;
	cout<<ans;
	return 0;
}



Measured memory_bytes: 3640
n = int(input())
a = list(map(int,input().split()))
b = []
c = [0 for _ in range(n)]

def make_divisors(n):
	lower_divisors , upper_divisors = [], []
	i = 1
	while i*i <= n:
		if n % i == 0:
			lower_divisors.append(i)
			if i != n // i:
				upper_divisors.append(n//i)
		i += 1
	return lower_divisors + upper_divisors[::-1]

#半分より上は, すべてa通り.
for i in range(1,n+1)[::-1]:
	if c[i-1] % 2 != a[i-1]:
		b.append(i)
		for j in make_divisors(i):
			c[j-1] += 1
print(len(b))
print(" ".join(list(map(str, b))))

Measured memory_bytes: 76008
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n)for(int i=0;i<(int)(n);i++)
#define PI 3.141592653589793
//vector < vector<int>>a(0, vector<int>(0));二次元配列宣言


int main()
{
    long long int sum = 0;
    int i, j, h,g;
    int k;
    cin >> k;
    for (i = 1; i <= k; i++)
    {
        for (j = 1; j <= k; j++)
        {
            for (h = 1; h <= k; h++)
            {
                for (g = min(min(i, j), min(j, h)); g >= 1; g--)
                {
                    if (i % g == 0 && j % g == 0 && h % g == 0)
                    {
                        sum += g;
                        break;
                    }
                }
            }
        }
    }
    cout << sum << endl;
    
}

Measured memory_bytes: 3576
#include <stdio.h>
#include <stdlib.h>

int main(void) {
  int row, column;
  char **table;

  scanf("%d %d", &row, &column);
  
  table = (char**)calloc(row, sizeof(char*));
  if(table == NULL){
    exit(1);
  }

  for(int i = 0; i < row; i++){
    table[i] = (char*)calloc(column+1, sizeof(char));
    if(table[i] == NULL){
      exit(1);
    }
  }

  

  for(int i = 0; i < row; i++){
    scanf("%s", table[i]);
  }

  for(int i = 0; i < row; i++){
    for(int j = 0; j < column; j++){
      if(table[i][j] == '#') break;
      if(j == column-1){
        for(int k = 0; k < column; k++){
          table[i][k] = '*';
        }
      }
    }
  }

  for(int i = 0; i < column; i++){
    for(int j = 0; j < row; j++){
      if(table[j][i] == '#') break;
      if(j == row-1){
        for(int k = 0; k < row; k++){
          table[k][i] = '*';
        }
      }
    }
  }


  for(int i = 0; i < row; i++){
    int judge = 0;
    for(int j = 0; j < column; j++){
      if(table[i][j] != '*'){
        printf("%c", table[i][j]);
        judge = 1;
      }
    }
    if(judge == 1) putchar('\n');
  }


  for(int i = 0; i < row; i++){
    free(table[i]);
  }
  free(table);


  return 0;
}

Measured memory_bytes: 1660
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;

class Program
{
	static void Main(string[] args)
	{
		string[] nm = Console.ReadLine().Split();

		int n = int.Parse(nm[0]);
		int m = int.Parse(nm[1]);

		int[] cs = Console.ReadLine().Split().Select(str => int.Parse(str)).ToArray();

		int[] minCounts = new int[50001];

		// コイン1枚で実現できる金額には枚数1を入れておく
		for (int ci = 0; ci < m; ci++)
		{
			minCounts[cs[ci]] = 1;
		}

		// 1から順番に辿る
		for (int i = 1; i <= n; i++)
		{
			if (minCounts[i] > 0) continue;
			minCounts[i] = GetMinCounts(i, minCounts);
		}
		System.Console.WriteLine(minCounts[n]);
	}

	// Kを実現する最小コイン枚数を返す
	static int GetMinCounts(int k, int[] minCounts)
	{
		// 頭と後ろからの組み合わせで最小値を計算
		int min = k;
		for (int j = 1; j < k; j++)
		{
			if (k - j < j) return min;
			int current = minCounts[k - j] + minCounts[j];
			if (current < min) min = current;
		}
		return min;
	}
}



Measured memory_bytes: 9792
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <unordered_map>
#include <queue>
#include <bitset>
#include <limits>
#include <numeric>

using ld = long double;
using ll = long long int;
using ul = unsigned long long int;

namespace lamlib
{
	/* constant */
	constexpr double epsilon = std::numeric_limits<double>::epsilon();

	/* math */
	template<class T> inline T abs(const T &a){ return (a>0) ? a : -a; }
	ul inline digit(const ul &num){ return static_cast<ul>(std::log10(num+epsilon))+1; }

	/* algorithm */
	ul gcd(const ul &a,const ul &b) { return (!b) ? a : gcd(b,a%b); }
	ul lcm(const ul &a,const ul &b) { return (a/gcd(a,b))*b; } // a/gcd(a,b)*b <=> (a*b)/gcd(a,b)
	std::vector<bool> eratosthenes(const ul &n)
	{
		std::vector<bool> prime_candidate(n,true);
		prime_candidate[0] = prime_candidate[1] = false;
		for(ul i = 2;i*i < n;++i)
		{
			if(!prime_candidate[i]) continue;
			for(ul j = 2;i*j < n;++j) prime_candidate[i*j] = false;
		}
		return prime_candidate;
	}
	ll rho_method(const ll &n)
	{
		auto f = [&](const ll &xi){ return (xi*xi+1)%n; };
		ll x = 2, y = 2, d = 1;
		while(d == 1)
		{
			x = f(x);
			y = f(f(y));
			d = lamlib::gcd(lamlib::abs(x-y),n);
		}
		return d;
	}
	// 素因数分解(試し割)
	std::vector<ll> prime_factorization_trial(const ll &n)
	{
		ll num = n;
		std::vector<ll> prime;
		for(ll i = 2;i*i <= n;++i)
		{
			while((num%i) == 0)
			{
				prime.emplace_back(i);
				num /= i;
			}
		}
		if(num > 1) prime.emplace_back(num);
		return prime;
	}

	/* string */
	inline ul same_char_count(const std::string s,const char &ch){ return std::count(std::cbegin(s),std::cend(s),ch); }
}

// std::cout << std::fixed << std::setprecision(15) << std::endl;

int main(int argc,char *argv[])
{
	ll n,k;
	std::cin >> n >> k;

	std::vector<ll> p(n,0);
	for(ll i = 0;i < n;++i) std::cin >> p[i];

	std::sort(p.begin(), p.end());

	ll ans = 0;
	for(ll i = 0;i < k;++i)
	{
		ans += p[i];
	}

	std::cout << ans << std::endl;

	return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	vector<string> v(n);
	for(int i=0;i<n;++i)
	{
		cin>>v[i];
	}
	cout<<"AC x "<<count(v.begin(),v.end(),"AC")<<"\n";
	cout<<"WA x "<<count(v.begin(),v.end(),"WA")<<"\n";
	cout<<"TLE x "<<count(v.begin(),v.end(),"TLE")<<"\n";
	cout<<"RE x "<<count(v.begin(),v.end(),"RE");
}


Measured memory_bytes: 6352
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
  vector<int> same;
  string S, T;
  cin >> S >> T;
  int end = S.length() - T.length();
  for (int i = 0; i <= end; ++i) {
    int counter = 0;
    for (int j = 0; j < T.length(); ++j) {
       if (S[i + j] == T[j])
         ++counter;
    }
    same.push_back(counter);
    if (counter == T.length())
      break;
  }
  cout << T.length() - *max_element(same.begin(), same.end()) << endl;
  return 0;
}

Measured memory_bytes: 3636
#include <stdio.h>
#include <stdlib.h>

int main() {
  int k, a, b;
  scanf("%d %d %d", &k, &a, &b);
  for(int i=a;i<=b;i++){
    if(i%k==0) {
      printf("OK"); 
      return 0;
    }
  }
  printf("NG");
  return 0;
}

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

int main(){
  string n;
  cin >> n;
  int a = n[0]-'0';
  int b = n[1]-'0';
  int c = n[2]-'0';
  int d = n[3]-'0';
  for(int i = 0; i < 8; i++){
    int op1 = 1& i>>2;
    int op2 = 1& i>>1;
    int op3 = 1& i;
    int ans = a + ((op1==0)?b:-b) + ((op2==0)?c:-c) + ((op3==0)?d:-d);
    if(ans==7){
      cout << a << ((op1==0)?'+':'-') << b << ((op2==0)?'+':'-') << c << ((op3==0)?'+':'-') << d << "=7" << endl;
      return 0;
    }
  }
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

int main(){
	int N;
	scanf("%d", &N);
	if((N % 1000) % 111 == 0 || (N / 10) % 111 == 0){
		printf("Yes\n");
	}
	else{
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 128
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCorder
{
    class Program
    {
        static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }


        public void Solve(ConsoleInput cin)
        {
            var N = cin.ReadInt;
            var rout = (int)Sqrt(N);
            WriteLine(rout * rout);
        }

        public class ConsoleInput
        {
            private readonly System.IO.TextReader _stream;
            private char _separator = ' ';
            private Queue<string> inputStream;
            public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
            {
                this._separator = separator;
                this._stream = stream;
                inputStream = new Queue<string>();
            }
            public string Read
            {
                get
                {
                    if (inputStream.Count != 0) return inputStream.Dequeue();
                    string[] tmp = _stream.ReadLine().Split(_separator);
                    for (int i = 0; i < tmp.Length; ++i)
                        inputStream.Enqueue(tmp[i]);
                    return inputStream.Dequeue();
                }
            }
            public string ReadLine { get { return _stream.ReadLine(); } }
            public int ReadInt { get { return int.Parse(Read); } }
            public long ReadLong { get { return long.Parse(Read); } }
            public double ReadDouble { get { return double.Parse(Read); } }
            public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
            public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
            public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
        }
    }
}


Measured memory_bytes: 11220
#include<bits/stdc++.h>
using namespace std;
#define pb push_back

int K;

/*dp[i][j] := i桁以下の最上位数がjのルンルン数(0も含む)*/
vector<vector<int>> dp(15, vector<int>(10, 0)); 
vector<int> cumulS(15, 0); //lln's cumulative S
vector<char> lln;  //LunLun number...


void LunLunNumber(int U, int digit){  //digit桁llnの下からU番目
    int tmp = 0, i = 1;
    while(digit > 0){     //digit桁目を決定しi
        while(tmp+dp[digit][i] < U) tmp += dp[digit][i++];
        lln.pb('0'+i);
        U -= tmp;         //次はdigit桁がiである下からU番目のlln
        --digit;
        tmp = 0, i -= 1;  //下の桁の数はi-1,i,i+1のいずれか
    }
    return ;
}


int main(){
    cin >> K;

    dp[1] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};  //初期条件

    int k = 9, d = 1;  //d桁以下のルンルン数の個数和がk
    while(k < K){
        cumulS[d] = k;  //d桁以下のルンルン数総数
        ++d;
        dp[d][0] = dp[d-1][0]+dp[d-1][1];  //ルンルン数ではない
        dp[d][9] = dp[d-1][8]+dp[d-1][9];  k += dp[d][9];
        for(int i = 1; i <= 8; i++){
            dp[d][i] = dp[d-1][i-1]+dp[d-1][i]+dp[d-1][i+1];
            k += dp[d][i];
        }
    }
    /*この時点でルンルン数はd桁であることが判明*/
    /*d桁のルンルン数の小さい方からK-cumulS[d]番目の数を出力*/
    LunLunNumber(K-cumulS[d-1], d);
    for(int i = 0; i < lln.size(); i++) cout << lln[i];
    cout << endl;
    return 0;
}






Measured memory_bytes: 3612
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
		int a=scan.nextInt();
		int b=scan.nextInt();
		if(a>b) {
			System.out.println(a-1);
		}
		else {
			System.out.println(a);
		}

	}

}

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

bool solve();

int main()
{
	if (solve()) puts("YES");
	else puts("NO");

	return 0;
}

bool solve()
{
	int H, W, N, s[2];
	scanf("%d%d%d%d%d", &H, &W, &N, s, s + 1);
	std::string S, T;
	std::cin >> S >> T;
	s[0]--;
	s[1]--;

	int left{-1}, right{W}, top{-1}, down{H};
	for (int i{N - 1}; i >= 0; i--)
	{
		if (T[i] == 'L')
			right = std::min(right + 1, W);
		else if (T[i] == 'R')
			left = std::max(left - 1, -1);
		else if (T[i] == 'U')
			down = std::min(down + 1, H);
		else
			top = std::max(top - 1, -1);
			
		if (S[i] == 'L')
			left = left + 1;
		else if (S[i] == 'R')
			right = right - 1;
		else if (S[i] == 'U')
			top = top + 1;
		else
			down = down - 1;
		if (left + 1 == right || top + 1 == down)
			return false;
	}
	return top < s[0] && s[0] < down && left < s[1] && s[1] < right;
}

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

using namespace std;

using ll = long long;

const ll MOD = 1000000007;

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

ll dp[10005][100][2];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	string K;
	int D;
	cin >> K >> D;
	dp[0][0][1] = 1;
	int n = K.size();
	for (int i = 0; i < n; i++) {
		int digit = K[i] - '0';
		for (int j = 0; j < D; j++) {
			for (int k = 0; k <= 9; k++) {
				(dp[i + 1][(j + k) % D][0] += dp[i][j][0]) %= MOD;
			}

			for (int k = 0; k < digit; k++) {
				(dp[i + 1][(j + k) % D][0] += dp[i][j][1]) %= MOD;
			}
			dp[i + 1][(j + digit) % D][1] += dp[i][j][1];
		}
	}

	cout << (dp[n][0][0] + dp[n][0][1] + MOD - 1) % MOD << endl;
	return 0;
}

Measured memory_bytes: 15872