akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD =998244353;
const ll MAX = 1000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

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

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

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};


///////////////////////////

ll N, Q;
vector<char> s;

vector<char> t, d;

ll ch(ll pos) {
	repn(i, Q) {
		if (s[pos] == t[i]) {
			if (d[i] == 'L') { pos--; }
			else { pos++; }
		}
	}

	if (pos == 0) { return 0; }
	if (pos == N + 1) { return 2; }
	return 1;
}



int main() {
	cin >> N >> Q;
	s.resize(N + 2);
	t.resize(Q + 1);
	d.resize(Q + 1);

	s[0] = '?';
	s[N + 1] = '?';
	repn(i, N) cin >> s[i];

	repn(i, Q) { cin >> t[i] >> d[i]; }

	ll l = 0;
	ll r = N + 1;
	while (r - l > 1) {
		ll m = (r + l) / 2;
		if (ch(m) >= 1) { r = m; }
		else { l = m; }
	}

	ll left = l;

	l = 0;
	r = N + 1;
	while (r - l > 1) {
		ll m = (r + l) / 2;
		if (ch(m) ==2) { r = m; }
		else { l = m; }
	}

	ll right=r;
	
	cout << right - left - 1;
	system("PAUSE");
}


Measured memory_bytes: 1024
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
  
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
  
using namespace std;
  
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
  
const int INF=1<<29;
const double EPS=1e-9;
  
const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};

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

int dp[401][401];
int main() {
    for(int i = 0; i < 401; i++) {
        for (int j = 0; j < 401; j++) {
            dp[i][j] = INF;
        }
    }
    int N, Ma, Mb;
    cin >> N >> Ma >> Mb;
    vector<int> A, B, C;
    for (int i = 0; i < N; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        A.push_back(a);
        B.push_back(b);
        C.push_back(c);
    }
    dp[0][0] = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 400; j >= 0; j--) {
            for (int k = 400; k >= 0; k--) {
                if (j + A[i] >= 400 || k + B[i] >= 400) continue;
                dp[j + A[i]][k + B[i]] = min(dp[j + A[i]][k + B[i]], dp[j][k] + C[i]);
            }
        }
    }

    int g = gcd(Ma, Mb);
    Ma /= g;
    Mb /= g;
    int Ma_ = Ma;
    int Mb_ = Mb;

    int ans = INF;
    while(Ma < 401 && Mb < 401) {
        ans = min(ans, dp[Ma][Mb]);
        Ma += Ma_;
        Mb += Mb_;
    }
    if (ans == INF) {
        cout << "-1" << endl;
    } else {
        cout << ans << endl;
    }



    return 0;
}

Measured memory_bytes: 896
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();
		if(A<=8&&B<=8) {
			System.out.println("Yay!");
		}else {
			System.out.println(":(");
		}
	}

}


Measured memory_bytes: 21716
#include <stdio.h>
 
//#define getchar_unlocked()  getchar()
int in()
{
    int n = 0, c = getchar_unlocked();
    do n = 10*n + (c & 0xf), c = getchar_unlocked(); while (c >= '0');
    return n;
}
 
int main()
{
    int n, a, min, ans;
 
    n = in()-2;
    min = in(), a = in();
    ans = a-min;
    if (a < min) min = a;
    while (n--) {
        a = in();
        if (a < min) min = a;
        else if (a-min > ans) ans = a-min;
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 2112
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define rrep(i, a, b) for (int i = a; i >= (b); i--)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <class T>
inline bool chmin(T& a, T 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 = 2e9;
const int MOD = 1e9 + 7;

int main() {
   int n;
   string s;
   cin >> n >> s;
   int ans = 0;
   rep(i, 0, 1000) {
      string t;
      int x = i;
      rep(j, 0, 3) {
         t += '0' + x % 10;
         x /= 10;
      }
      reverse(t.begin(), t.end());
      int ti = 0;
      rep(j, 0, n) {
         if (s[j] == t[ti]) ti++;
         if (ti == 3) break;
      }
      if (ti == 3) ans++;
   }
   cout << ans << endl;
   return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#define MN 200000
#define MM 200000
#define INF 0x7fffffff
int n,m,a[MN+5];
int hd[MN+5],nxt[MM+5],to[MM+5],rn=0;
int mi1,mi2,lc=0,l[MN+5],lft=2,cnt=0;
long long ans=0;
bool usd[MN+5],usd2[MN+5];
inline void add(int u,int v){
	++rn;
	nxt[rn]=hd[u],hd[u]=rn;
	to[rn]=v;
}
void dfs(int u){
	usd[u]=true;
	if(a[u]<mi1){
		mi1=a[u];
		mi2=u;
	}
	for(int i=hd[u];i!=-1;i=nxt[i])
		if(!usd[to[i]]) dfs(to[i]);
}
int main(){
	memset(hd,0xff,sizeof(hd));
	memset(usd,0,sizeof(usd));
	memset(usd2,0,sizeof(usd2));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=m;i++){
		int u,v; scanf("%d%d",&u,&v);
		u++,v++; add(u,v),add(v,u);
	}
	for(int i=1;i<=n;i++){
		mi1=INF;
		if(!usd[i]) dfs(i);
		else continue;
		cnt++;
		ans+=mi1; usd2[mi2]=true;
	}
	if(cnt==1) puts("0"),exit(0);
	for(int i=1;i<=n;i++)
		if(!usd2[i]) l[++lc]=a[i];
	if(lc<(n-1-m)*2-cnt) puts("Impossible"),exit(0);
	std::sort(l+1,l+1+lc);
	for(int i=1;i<=(n-1-m)*2-cnt;i++)
		ans+=l[i];
	printf("%lld",ans);
}

Measured memory_bytes: 3840
n=int(input())
F=[int(input().replace(' ',''),2) for i in range(n)]
P=[list(map(int,input().split())) for i in range(n)]
ans=-10**10
 
for i in range(1,2**10):
  a=0
  for f,p in zip(F,P):
    a+=p[bin(f&i).count('1')]
  ans=max(ans,a)
print(ans)

Measured memory_bytes: 41580
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

#ifdef WIN32
	#define LL "%I64d"
#else
	#define LL "%lld"
#endif

#ifdef CT
	#define debug(...) printf(__VA_ARGS__)
	#define setfile() 
#else
	#define debug(...)
	#define filename ""
	#define setfile() freopen(filename".in", "r", stdin); freopen(filename".out", "w", stdout)
#endif

#define R register
#define getc() (S == T && (T = (S = B) + fread(B, 1, 1 << 15, stdin), S == T) ? EOF : *S++)
#define dmax(_a, _b) ((_a) > (_b) ? (_a) : (_b))
#define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))
#define cmax(_a, _b) (_a < (_b) ? _a = (_b) : 0)
#define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0)
#define cabs(_x) ((_x) < 0 ? (- (_x)) : (_x))
char B[1 << 15], *S = B, *T = B;
inline int F()
{
	R char ch; R int cnt = 0; R bool minus = 0;
	while (ch = getc(), (ch < '0' || ch > '9') && ch != '-') ;
	ch == '-' ? minus = 1 : cnt = ch - '0';
	while (ch = getc(), ch >= '0' && ch <= '9') cnt = cnt * 10 + ch - '0';
	return minus ? -cnt : cnt;
}
#define maxn 100010
int a[maxn];
int main()
{
//	setfile();
	R int n = F();
	for (R int i = 1; i <= n; ++i)
		a[i] = F();
	std::sort(a + 1, a + n + 1);
	R int num = 0, cnt = 0;
	for (R int i = 1; i <= n; ++i)
		if (a[i] == a[i - 1]) cnt ^= 1;
		else ++num;
	printf("%d\n", num - cnt );
	return 0;
}


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<string> vs;
typedef pair<int, int> P;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

void YN(bool flg){if(flg) cout << "YES" << endl; else cout << "NO" << endl;}
void Yn(bool flg){if(flg) cout << "Yes" << endl; else cout << "No" << endl;}
void yn(bool flg){if(flg) cout << "yes" << endl; else cout << "no" << endl;}

//素因数分解
vector<pair<ll, int>> factorize(ll n) {
    vector<pair<ll, int>> res;
    for(ll i = 2; i * i <= n; i++) {
        if(n % i) continue;
        res.emplace_back(i, 0);
        while(n % i == 0) {
            n /= i;
            res.back().second++;
        }
    }
    if(n != 1) res.emplace_back(n, 1);
    return res;
}

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

    vector<pair<ll, int>> f = factorize(n);
    
    ll ans = 0;
    for(auto u : f) {
        int num = u.second;
        int i = 1;
        while(i <= num) {
            num -= i;
            ans++;
            i++;
        }
    }

    cout << ans << endl;

    return 0;
}


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

using namespace std;

using ll = long long;
#define long long long

int main(void) {
    constexpr ll MOD = 1e9 + 7;
    cout << setprecision(16) << fixed;

    ll n;
    cin >> n;
    string s;
    cin >> s;

    vector<vector<ll>> dp(n+1, vector<ll>(n));
    dp[0][0] = 1;
    for(ll i=0; i<n; i++) {
        partial_sum(dp[i].begin(), dp[i].end(), dp[i].begin(),
                [&](ll a, ll b){return (a+b) % MOD;});
        for(ll j=0; i+j<n; j++) {
            if(s[i] == '<')
                (dp[i+1][j] += dp[i][j]) %= MOD;
            else {
                (dp[i+1][0] += dp[i][j]) %= MOD;
                (dp[i+1][j] += MOD - dp[i][j]) %= MOD;
            }
        }
    }

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


Measured memory_bytes: 70784
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    static int N;
    static int K;
    static List<Integer> A = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();

        for (int i = 0; i < N; i++) {
            int Ai = sc.nextInt();
            A.add(Ai);
        }

        solve();
    }

    static void solve() {
        // 最初1を含むK個を選んだあと、
        // 残りの(N-K)個から(K-1)個のグループがいくつできるか
        // (a+b-1)/b

        int answer = 1 + (((N - K) + (K - 1) - 1) / (K - 1));
        System.out.println(answer);
    }
}


Measured memory_bytes: 55744
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N; cin >> N;
	vector<int> A(N); rep(i, 0, N) {
		cin >> A[i];
	}
	int sum = accumulate(all(A), 0);
	static bitset<2001 * 2001> s;
	s.set(0);
	rep(i, 0, N)
		s |= s << A[i];
	int ans = sum / 2 + !!(sum % 2);
	while (!s[ans])ans++;
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
long long int n,m;
double ans;
double dp[3001][3001];
double arr[3002];
double solve(long long int x,long long int y)
{
    if(x>n||x<0)
        return 0;
    if(y>n||y<0)
        return 0;
    if((x+y)>n)
        return 0;
    if((x+y)==n)
    {
       if(x>y)    
        return 1;
       else
        return 0;
    }    
    if(dp[x][y]!=-1)
        return dp[x][y];
    dp[x][y]=(((arr[x+y+1]*solve(x+1,y))+((1-arr[x+y+1])*solve(x,y+1))));
    return dp[x][y];
}
int main()
{
    long long int k,a,b,i,j;
    char ch;
    cin >> n;
    //cin >> ch;
    for(i=1;i<=n;i++) 
    {
        cin >> arr[i];
    }
   for(i=0;i<3001;i++)
    for(j=0;j<3001;j++)
        dp[i][j]=-1;
   //cout << n << m; 
    ans=(arr[1]*solve(1,0))+((1-arr[1])*solve(0,1));
   printf("%0.10lf\n",ans);
   /*for(i=1;i<=n;i++)
   {
    for(j=1;j<=m;j++)
        cout << arr[i][j];
    cout << endl;
   }*/
   return 0;
}

Measured memory_bytes: 70784
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>


long int N,K,Q,A[100001];


int main()
{
  
  long int i,j;
  scanf("%ld %ld %ld",&N,&K,&Q);
  
  for(i=0;i<N;i++)
  {
    A[i]=0;
  }
  
  for(i=0;i<Q;i++)
  {
    scanf("%d",&j);
    j--;
    A[j]++;
  }
  
  for(i=0;i<N;i++)
  {
    if(K-Q+A[i]>0)
    {
      printf("Yes\n");
    }
    else
    {
      printf("No\n");
    }
  }
  
 return 0; 
}

Measured memory_bytes: 1280
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <utility>
#include <tuple>

using namespace std;

int main()
{
    long long k, a, b;
    cin >> k >> a >> b;
    long long ans = 0;
    if(k < a){
        // cout << "case1" << endl;
        ans = 1 + k;
    }
    // k >= a : include exchange
    else {
        if(b - a <= 2){
            // cout << "case2" << endl;
            ans = 1 + k;
        }
        else {
            long long n = (k - a + 1) / 2;
            if((k - a + 1) % 2 == 0){
                // cout << "case3" << endl;
                ans = b + (n-1) * (b-a);
            }
            else {
                ans = b + 1 + (n-1) * (b-a);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
ll arr[100100],n,k,ans,a,b,temp;
map<ll,ll> mp;
int main()
{
    cin>>n>>k;
    while(k--)
    {
        cin>>a>>b;
        mp[a]++,mp[b]++;
    }
    for(map<ll,ll> :: iterator it=mp.begin();it!=mp.end();it++)
    {
        if((*it).second%2!=0)
        {
            cout<<"NO"<<endl;
            return 0;
        }
    }
    cout<<"YES"<<endl;
return 0;
}


Measured memory_bytes: 5632
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
# map(int, input().split())
# int(input())
# input().split()
# mojiretu = ','.join(str_list)
# sorted(input())

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(1, n-1):
    if sorted(a[i-1: i+2])[1] == a[i]:
        ans += 1
print(ans)

Measured memory_bytes: 5048
import sys
k = int(input())
klist=list(map(str, [1,2,3,4,5,6,7,8,9]))
dic = {'0':['0','1'], '1':['0','1','2'], '2':['1','2','3'], '3':['2','3','4'], '4':['3','4','5'], '5':['4','5','6'], '6':['5','6','7'], '7':['6','7','8'], '8':['7','8','9'], '9':['8','9']}
if k <= 9:
    print(klist[k-1])
    sys.exit()
else:
    count = 0
    ok = 9
    while 1:
        tmp = klist[count]
        for add in dic[tmp[-1]]:
            klist.append(''.join([tmp, add]))
            ok+=1
            if ok == k:
                print(''.join([tmp, add]))
                sys.exit()
        count+=1

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

ll MOD = 1000000007;

int main()
{
  string l;
  cin >> l;
  vector<ll> pow3(l.size());
  int s = l.size();
  rep(i, s)
    if (i == 0)
      pow3[0] = 1;
    else
      pow3[i] = pow3[i-1] * 3 % MOD;
  ll ans = 0;
  ll c = 1;
  for (char i : l)
  {
    s--;
    if (i == '1')
    {
      ans = (ans + c * pow3[s]) % MOD;
      c = c * 2 % MOD;
    }
  }
  ans = (ans + c) % MOD;
  cout << ans << endl;
  return 0;
}

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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

typedef pair<int,int> pi;

struct edge{int to,cost;};
const int INF=12345678;

vector<edge> G[2000];

int d[2000][2000];

int main()
{
    int n,k;
    cin >>n >>k;

    vector<pi> E;

    rep(i,n-1)
    {
        int a,b;
        cin >>a >>b;
        --a;
        --b;

        G[a].pb(edge{b,1});
        G[b].pb(edge{a,1});
        E.pb(pi(a,b));
    }

    fill(d[0],d[2000],INF);
    rep(i,n)
    {
        //dijkstra
        priority_queue<pi,vector<pi>,greater<pi>> que;
        d[i][i]=0;
        que.push(pi(0,i));
        while(!que.empty())
        {
            pi p=que.top();
            que.pop();
            int v=p.se;

            if(d[i][v]<p.fi) continue;

            rep(j,G[v].size())
            {
                edge e=G[v][j];
                if(d[i][e.to]>d[i][v]+e.cost)
                {
                    d[i][e.to]=d[i][v]+e.cost;
                    que.push(pi(d[i][e.to],e.to));
                }
            }
        }
    }

    int ans=n;

    if(k%2==0)
    {
        rep(i,n)
        {
            int ct=0;
            rep(j,n) if(d[i][j]>k/2) ++ct;
            ans=min(ans,ct);
        }
    }
    else
    {
        rep(i,E.size())
        {
            int va=E[i].fi;
            int vb=E[i].se;

            int ct=0;
            rep(j,n) if(d[va][j]>(k-1)/2 && d[vb][j]>(k-1)/2) ++ct;
            ans=min(ans,ct);
        }
    }

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


Measured memory_bytes: 16000
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int h,w,m;
  cin >> h >> w >> m;
  vector<int>a(m);
  vector<int>b(m);
  vector<int>hn(h);
  vector<int>wn(w);
  vector<bool>wb(w);
  vector<bool>hb(h);
  for (int i=0;i<m;i++) {
    cin >> a.at(i) >> b.at(i); 
    hn[a[i]-1]++;
    wn[b[i]-1]++;
  }
  int hmax=0;
  int wmax=0;
  long long hmaxn=0;
  long long wmaxn=0;
  for (int i=0;i<h;i++) {
    if(hmax<hn[i]){
      hmax=hn[i];
    } 
  }
  for (int i=0;i<w;i++) {
    if(wmax<wn[i]){
      wmax=wn[i];
    } 
  }
  for (int i=0;i<h;i++) {
    if(hn[i]==hmax){
      hmaxn++;
      hb[i]=true;
    } 
  }
  for (int i=0;i<w;i++) {
    if(wmax==wn[i]){
      wmaxn++;
      wb[i]=true;
    } 
  } 
  if(hmaxn*wmaxn>300000){
    cout << hmax+wmax << endl;
    return 0;
  }
  int count=hmaxn*wmaxn;
  for (int i=0;i<m;i++) {
    if(hb[a[i]-1]==true && wb[b[i]-1]==true ){
      count--;
    }
    if(count==0){
      cout << hmax+wmax-1 << endl;
      return 0;
    }
  }
  cout << hmax+wmax << endl;
}

Measured memory_bytes: 7988
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = 0; i <= (n); i++)
using namespace std;
typedef long long ll;
 
const ll INF = 1LL<<60;
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; }
using Graph = vector<vector<int>>;

typedef pair<int, int> P;
typedef priority_queue<int, vector<int>, greater<int>> PQ;
const int MOD = 1000000007;

const int maxv = 100005;




int main(){
    string s, t;
    map<char, vector<int>> counter;
    cin >> s >> t;

    rep(i,s.size()){
        int index = i+1;
        // 各文字毎の出現位置を格納
        counter[s[i]].push_back(index);
    }

    ll ans = 0;
    int prev_index;
    // tの文字数分繰り返す
    rep(i, t.size()){
        char ch = t[i];
        // Sに登場しなかった場合は終了
        if (counter[ch].empty()){
            cout << -1 << endl;
            return 0;
        }
        if (i == 0) {
            prev_index = counter[ch][0];
            ans = prev_index;
            continue;
        }
        else{
            int size = counter[ch].size();
            vector<int> c = counter[ch];
            int next_index;
            if (prev_index >= c[size-1]){
                next_index = c[0];
            }
            else{
                int c_index = upper_bound(c.begin(), c.end(), prev_index) - c.begin();
                
                ll ng = -1;
                ll ok = c.size();
                
                while(abs(ok-ng)>1){
                    ll mid = (ok+ng) / 2;
                
                    if(c[mid] > prev_index) ok = mid;
                    else ng = mid;
                }

                next_index = c[c_index];
            }

           if (prev_index < next_index){
                ans += next_index - prev_index;
            }else{
                ans += next_index + (s.size() - prev_index);
            }
            prev_index = next_index;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 4512
#include <iostream>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

const ll MOD = 998244353;

ll modpow(ll x, ll n){
    ll res = 1, r = x;
    while(n){
        if(n % 2) res = res * r % MOD;
        r = r * r % MOD;
        n /= 2;
    }
    return res;
}

int main()
{
    ll n;
    int m;
    cin >> n >> m;
    int a[50005], b[50005], c[50005];
    int d[100002];
    fill(d, d + n, -1);
    int e[100002];
    fill(e, e + n, -1);
    for(int i = 0; i < m; i++){
        cin >> a[i] >> b[i] >> c[i];
        a[i]--; b[i]--;
        if(a[i] == b[i]) d[a[i]] = c[i];
    }
    map<P, int> mp;
    ll k = n * (n - 1) / 2;
    for(int i = 0; i < m; i++){
        if(a[i] == b[i]) continue;
        int j = mp[P(b[i], a[i])] - 1;
        if(j >= 0){
            if(abs(a[i] - b[i]) > 2){
                if(c[i] != c[j]){
                    cout << 0 << endl;
                    return 0;
                }
            }
            if(abs(a[i] - b[i]) == 2){
                if(d[(a[i] + b[i]) / 2] == -1) d[(a[i] + b[i]) / 2] = (c[i] + c[j]) % 2;
                else if(d[(a[i] + b[i]) / 2] != (c[i] + c[j]) % 2){
                    cout << 0 << endl;
                    return 0;
                }
            }
            if(abs(a[i] - b[i]) == 1){
                e[max(a[i], b[i])] = (c[i] + c[j]) % 2;
            }
        }
        else{
            mp[P(a[i], b[i])] = i + 1;
            k--;
        }
    }
    queue<int> que;
    for(int i = 0; i < n; i++){
        if(d[i] != -1) que.push(i);
    }
    while(que.size()){
        int i = que.front();
        que.pop();
        if(i > 0 && e[i] != -1){
            if(d[i - 1] == -1){
                d[i - 1] = (d[i] + e[i]) % 2;
                que.push(i - 1);
            }
            else if(d[i - 1] != (d[i] + e[i]) % 2){
                cout << 0 << endl;
                return 0;
            }
        }
        if(i < n - 1 && e[i + 1] != -1){
            if(d[i + 1] == -1){
                d[i + 1] = (d[i] + e[i + 1]) % 2;
                que.push(i + 1);
            }
            else if(d[i + 1] != (d[i] + e[i + 1]) % 2){
                cout << 0 << endl;
                return 0;
            }
        }
    }
    for(int i = 1; i < n; i++){
        if(e[i] != -1 && d[i] == -1) k--;
    }
    for(int i = 0; i < n; i++){
        if(d[i] == -1) k++;
    }
    cout << modpow(2, k) << endl;
}


Measured memory_bytes: 11216
#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    def divisors(x):
        r1 = deque()
        r2 = deque()
        for i in range(1,ceil(x**0.5)):
            if x % i == 0:
                r1.append(i)
                r2.appendleft(x//i)
        if int(x**0.5) == x**0.5:
            r1.append(int(x**0.5))
        return list(r1)+list(r2)
    #N-1の約数
    ans = len(divisors(N-1))-1
    # print(ans)
    # print(divisors(N))
    for d in divisors(N)[1:]:
        tmpN = N
        while tmpN % d == 0:
            tmpN //= d
        if tmpN % d == 1:
            ans += 1

            
            
    print(ans)


    

if __name__ == '__main__':
    main()

Measured memory_bytes: 64748
#include<stdio.h>

int main(void)
{
  long long min=10000;
  long long l,r;
  scanf("%lld %lld",&l,&r);


  for(long long i=l;i<r;i++){
    for(long long j=l+1;j<=r;j++){

      if((i*j)%2019<min){
        min=(i*j)%2019;
        if(min==0){
          puts("0");
          return 0;
        }
      }
    }
  }

  printf("%lld\n",min);
  return 0;
}


Measured memory_bytes: 128
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,t = map(int,ipt().split())
    dp = [[0,0] for i in range(t)]
    for _ in range(n):
        a,b = map(int,ipt().split())
        for i in range(t-1,a-1,-1):
            di = dp[i][1]
            dpi = dp[i-a][1]+b
            if di < dpi:
                dp[i][1] = dpi
        for i in dp:
            if i[1] < i[0]+b:
                i[1] = i[0]+b
        for i in range(t-1,a-1,-1):
            di = dp[i][0]
            dpi = dp[i-a][0]+b
            if di < dpi:
                dp[i][0] = dpi

    print(dp[t-1][1])

    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 71060
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second
 
const int mx=200010;
const ll mod=1e9+7;

//snuke
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint& operator+=(const mint a) { if ((x += a.x) >= mod) x -= mod; return *this; }
  mint& operator-=(const mint a) { if ((x += mod-a.x) >= mod) x -= mod; return *this; }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; }
  mint operator+(const mint a) const { mint res(*this); return res+=a; }
  mint operator-(const mint a) const { mint res(*this); return res-=a; }
  mint operator*(const mint a) const { mint res(*this); return res*=a; }
  mint pow(ll t) const { if (!t) return 1; mint a = pow(t>>1); a *= a; if (t&1) a *= *this; return a; }
  // for prime mod
  mint inv() const { return pow(mod-2); }
  mint& operator/=(const mint a) { return (*this) *= a.inv(); }
  mint operator/(const mint a) const { mint res(*this); return res/=a; }
}; 

vector<ll> inv,fact,invfact;
void mod_build(int n){  
  fact.resize(n+1); inv.resize(n+1); invfact.resize(n+1);
  fact[0]=inv[0]=invfact[0]=1; inv[1]=1;
  rep(i,n){
    fact[i+1]=fact[i]*(i+1)%mod;
    if(i>0)inv[i+1]=mod-inv[mod%(i+1)]*(mod/(i+1))%mod;
    invfact[i+1]=invfact[i]*inv[i+1]%mod;
  }
}
ll perm(int n,int k){ if(n<0||k<0||k>n){ return 0; } else { return fact[n]*invfact[n-k]%mod; } }
ll comb(int n,int k){ if(n<0||k<0||k>n){ return 0; } else { return (fact[n]*invfact[n-k]%mod)*invfact[k]%mod; }}
ll powmod(ll n,ll k){
  k%=mod-1; if(k<0)k+=mod-1;
  ll ret=1; while(k){ if(k&1)ret=ret*n%mod; n=n*n%mod; k>>=1; }
  return ret;
}

int main(){  
  mod_build(201010);
  ll n,m,k;
  cin >> n >> m >> k;
  
  mint ans=0;
  rep(i,m){ ans += i*(m-i)*n*n; }
  ans *= comb(n*m-2,k-2);
  
  mint tmp=0;
  rep(i,n){ tmp += i*(n-i)*m*m; }
  tmp *= comb(n*m-2,k-2);
  
  ans += tmp;

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

Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
int main(){

  int N,x;

  cin>>N>>x;

  int a[101];
  
  for(int i=0;i<N;i++){
    cin>>a[i];
  }

  sort(a,a+N);

  int cnt=0;
  
  for(int i=0;i<N;i++){

    if(i==N-1){
      if(a[i]==x){
	cnt++;
      }
    }else{   
      if(a[i]<=x){
	x-=a[i];
	cnt++;
      }
    }
  }
    
  cout<<cnt<<endl;
  
  return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
#include <math.h>
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define INF 999999999
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

using llong = long long;
using namespace std;

// long long gcd(long long a, long long b){
//     if (a < b){
//         a ^= b;
//         b ^= a;
//         a ^= b;
//     }
//     return b ? gcd(b, a % b) : a;
// }

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

int main(){
    int n;
    cin >> n;
    int a,m[20][20],x,y,ans=0;
    rep(i,n) rep(j,n) m[i][j] = -1;
    rep(i,n){
        cin >> a;
        rep(j,a){
            cin >> x >> y;
            x--;
            m[i][x] = y;
        }
    }
    rep(i,1<<n){
        vector<int> d(n);
        bool ok = true;
        rep(j,n){
            if(i>>j&1) d[j] = 1;
            else d[j] = 0;
        }
        rep(j,n){
            if(d[j]){
                rep(k,n){
                    if(m[j][k] == -1) continue;
                    if(m[j][k] != d[k]) ok = false;
                }
            }
        }
        if(ok){
            ans = max(ans,__builtin_popcount(i));
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
K, A, B = gets.split.map(&:to_i)

if B - A <= 2
  puts K + 1
else
  exchange = (K - (A - 1)) / 2
  if ((K - (A - 1)) % 2 == 0)
    puts A + (B - A) * exchange
  else
    puts A + (B - A) * exchange + 1
  end
end


Measured memory_bytes: 1788
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
template<typename T>
ostream& operator<<(ostream& os, vector<T> const& v) {
  os << "[";
  for (size_t i = 0; i < v.size(); i++) {
    os << (i == 0 ? "" : ",") << v[i];
  }
  return os << "]";
}
template<typename S, typename T>
ostream& operator<<(ostream& os, pair<S, T> const& v) {
  return os << "<" << v.first << "," << v.second << ">";
}

typedef int64_t I;
typedef vector<I> vI;
typedef vector<vI> vvI;
typedef pair<int, int> II;
typedef vector<II> vII;

const I M = 998244353;
I inv(I a, I b) {
  I x0 = 1, y0 = 0, x1 = 0, y1 = 1;
  while (b != 0) {
    I q = a / b, nb = a % b;
    a = b;
    b = nb;
    I nx1 = x0 - q * x1, ny1 = y0 - q * y1;
    x0 = x1;
    x1 = nx1;
    y0 = y1;
    y1 = ny1;
  }
  while (x0 < 0) {
    x0 += M;
  }
  return x0;
}
 

I solve(vI const& a, I n, I s) {
  I r = 0;
  vI counts(s + 1, 0);
  counts[0] = 0;
  for (size_t i = 0; i < a.size(); i++) {
    counts[0]++;
    vI newcounts(counts);
    for (I j = 0; j < s; j++) {
      if (j + a[i] <= s) {
        newcounts[j + a[i]] = (newcounts[j + a[i]] + counts[j]) % M;
      }
    }
    //cerr << newcounts << "," << counts << endl;
    counts.swap(newcounts);
    r = (r + counts[s]) % M;
  }
  return r % M;
}

int main() {
  I n, s; cin >> n >> s;
  vI a(n);
  for (size_t i = 0; i < a.size(); i++) cin >> a[i];
  cout << solve(a, n, s) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h> 
#define lb lower_bound 
#define ub upper_bound 
#define sqr(x) (x)*(x) 
#define lowbit(x) (x)&(-x) 
#define mem(a,x) memset(a,x,sizeof(a));
using namespace std; 
typedef long long ll;

const ll mo = 1e9+7;

ll po(ll a,ll b,ll p){
	ll ans = 1;
	while(b){
		if(b&1){
			ans *= a;
			ans %= p;
		}
		b /= 2;
		a *= a;
		a %= p;
	}
	return ans;
}

int main(){
	ll n;
	scanf("%lld",&n);
	if(n==1) puts("0");
	else if(n==2) puts("2");
	else{
		ll ans = po(10,n,mo);
		ans -= po(9,n,mo);
		ans += mo;
		ans %= mo;
		ans -= po(9,n,mo);
		ans += mo;
		ans %= mo; 
		ans += po(8,n,mo);
		ans %= mo;
		printf("%lld\n",ans);
	}
} 

Measured memory_bytes: 3824
#include <bits/stdc++.h>
#define fast_in_out     ios_base::sync_with_stdio(false);cin.tie(0);
#define nl              printf("\n")
using namespace std;
int main()
{
    fast_in_out
    string s,t;
    int ap=0;
    cin>>s;
    while(cin>>t)
    {
        bool jabe=true;
        if(t=="END_OF_TEXT")break;
        int i;
        for(i=0;i<t.size();i++)
        {
            if(t[i]>='A'&&t[i]<='Z')t[i]=t[i]-'A'+'a';
        }
        if(s==t){
            ap++;
        //cout<<t<<'\n';
        }

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



Measured memory_bytes: 3160
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <climits>

using namespace std;

int cnt[507][507];

int main(){
	int n,m,q;
	scanf("%d%d%d",&n,&m,&q);
	for (int i=1;i<=m;i++) {
		int L,R;
		scanf("%d%d",&L,&R);
		cnt[L][R]++;
	}
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++) cnt[i][j]+=cnt[i][j-1];

	while (q--) {
		int L,R;
		scanf("%d%d",&L,&R);
		int ans=0;
		for (int i=L;i<=R;i++) 
			ans+=cnt[i][R]-cnt[i][L-1];
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 1920
#
# abc075 b
#

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 5
.....
.#.#.
....."""
        output = """11211
1#2#1
11211"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3 5
#####
#####
#####"""
        output = """#####
#####
#####"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """6 6
#####.
#.#.##
####.#
.#..#.
#.##..
#.#..."""
        output = """#####3
#8#7##
####5#
4#65#2
#5##21
#4#310"""
        self.assertIO(input, output)


def resolve():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    A = [[0] * (W+2) for _ in range(H+2)]

    for y in range(H):
        for x in range(W):
            if S[y][x] == "#":
                for i in range(y, y+3):
                    for j in range(x, x+3):
                        A[i][j] += 1

    for y in range(H):
        for x in range(W):
            if S[y][x] == "#":
                print("#", end="")
            else:
                print(A[y+1][x+1], end="")
        print()


if __name__ == "__main__":
    # unittest.main()
    resolve()


Measured memory_bytes: 16292
#include<iostream>
using namespace std;
long long a,b,c,d,ans=0,n,m;
int main()
{
	cin>>a>>b>>c>>d>>n;
	n*=4;
	m=n/8;
	n-=m*8;
	ans+=m*min(min(a*8,b*4),min(c*2,d));
	m=n/4;
	n-=m*4;
	ans+=m*min(min(a*4,b*2),c);
	m=n/2;
	n-=m*2;
	ans+=m*min(min(a*2,b),min(c,d));
	m=n;
	ans+=m*min(min(a,b),min(c,d));
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

string s;
vector<string> ans;
bool used[26];
int n;
void dfs(string t,int cur){
    if(n==t.size()){
        ans.pb(t);return;
    }
    if(used[s[cur]-'a']){
        dfs(t+s[cur],cur+1);
    }
    if(s[cur]!='z'&&!used[s[cur]-'a'+1]){
        used[s[cur]-'a'+1]=true;
        dfs(t+(char)(s[cur]+1),cur+1);
        used[s[cur]-'a'+1]=false;
    }
}
int main(){
    while(cin>>s,s!="#"){
        n=s.size();
        ans.clear();
        memset(used,0,sizeof(used));
        used[0]=true;
        dfs("",0);
        sort(ans.begin(),ans.end());
        cout<<ans.size()<<endl;
        if(ans.size()<=10){
            rep(i,ans.size()) cout<<ans[i]<<endl;
        }
        else{
            rep(i,5) cout<<ans[i]<<endl;
            FOR(i,ans.size()-5,ans.size()) cout<<ans[i]<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 4332
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
using namespace std;

int MOD = 1000000007;
char m[1010][1010];
ll ans[1010][1010];
signed main(){
    ll h,w;
    cin >> h >> w;

    rep(i,h) rep(j,w) cin >> m[i][j];

    rep(i,h){
        rep(j,w){
            if(i == 0 && j == 0){
                ans[i][j] = 1;
            }else if(i == 0){
                if(m[i][j-1] == '.')ans[i][j] = ans[i][j-1];
                else ans[i][j] = 0;
            }else if(j == 0){
                if(m[i-1][j] == '.')ans[i][j] = ans[i-1][j];
                else ans[i][j] = 0;
            }else{
                if(m[i][j-1] == '.')ans[i][j] += ans[i][j-1];
                if(m[i-1][j] == '.')ans[i][j] += ans[i-1][j];
                ans[i][j] %= MOD;
            }
        }
    }
    cout << ans[h-1][w-1] << endl;


    
      
    return 0;
}

// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_a
// rm -r -f test;oj dl http://dp.contest.atcoder.jp/tasks/dp_f

Measured memory_bytes: 9216
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(),(x).end())
#define ALL(x) x.begin(),x.end()
#define db(x) cout<<#x<<"="<<x<<endl
#define rep(i, n) for(int i = 0; i < n; i++)
#define reps(i, m, n) for(int i = m; i < n; i++)
#define repr(i, n, m) for(int i = n; i >= m; i--)
#define INF (1e9)
#define PI (acos(-1))
using namespace std;
typedef long long ll;

int main(){

  int a,b;
  cin >> a>>b;

  cout << max((a*b),(max((a+b),(a-b)))) <<endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;
import java.lang.*;
class Mod{
    static final int MOD = 1000_000_007;
    static final int[] fact, factInv;
  	static {
      int size = 80_000_000;
      fact = new int[size];
      fact[0]=1;
      for(int i=1;i<fact.length;i++){
        fact[i]=mult(fact[i-1],i);
      }
      factInv = new int[size];
      factInv[size - 1] = inverse(fact[size - 1]);
      for (int i = size - 2;i >= 0;-- i) {
        factInv[i] = mult(factInv[i + 1], i + 1);
      }
    }

    public static int add(int a, int b){
        int tmp = (a+b)%MOD;
        return tmp>=0 ? tmp : tmp+MOD;
    }
    public static int adds(int... ar){
        int ans=0;
        for(int x:ar) ans = Mod.add(ans, x);
        return ans;
    }
    public static int sub(int a, int b){
        return add(a,-b);
    }
    public static int mult(int a, int b){
        int tmp = (int)((long)a*b%MOD);
        return tmp>=0 ? tmp : tmp+MOD;
    }
    public static int mults(int... ar){
        int ans=1;
        for(int x:ar) ans = Mod.mult(ans, x);
        return ans;
    }
    public static int power(int a, int x){ //calculate a^x
        if(x<0)return 0;
        if(x==0)return 1;
        if(x%2==0) {
            int half = power(a,x/2);
            return mult(half,half);
        }
        return (int)((long)a*power(a,x-1) % MOD);
    }
    public static int inverse(int a){
        return power(a,MOD-2);
    }
    public static int div(int a, int b){
        return mult(a, inverse(b));
    }
  	
    public static int combination(int n, int r){
        int N = n,  R = r;
        if(n<0 || r<0 || n<r) return 0;
        return mults(fact[N],factInv[R],factInv[N-R]);
    }
    public static int permutation(int n, int r){
        int N = n,  R = r;
        if(n<0 || r<0 || n<r) return 0;
        return mult(fact[N], factInv[N-R]);
    }
}

public class Main {
    static int count(int N, int K, int M){
        return Mod.power(K/M, N);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        long startTime = System.currentTimeMillis();
        int[] ans = new int[K+1];
        for(int k=K; k>0; k--){
            ans[k] = count(N, K, k);
            for(int i=2; i*k<=K; i++) ans[k] = Mod.sub(ans[k], ans[i*k]);
        }

        int total = 0;
        for(int k=1; k<=K; k++) total = Mod.add(total, Mod.mult(k, ans[k]));
        System.err.printf("%.3f sec\n", (System.currentTimeMillis()-startTime)*0.001);
        System.out.println(total);
    }
}


Measured memory_bytes: 667976
/*
    NEVER GIVE UP!
    THE EXPERT IN ANYTHING WAS ONCE A BEGINNER
*/

#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define f(i,a,b) for(ll i=a; i<=b; i++)
#define fi(i,a,b) for(ll i=a; i>=b; i--)
#define fa(x,b) for(auto x:b)
#define TC ll test_case; cin>>test_case; for(ll number=1 ; number <= test_case ; number ++ )
#define vll vector<ll>
#define pb push_back
#define pll pair<ll,ll>
#define mp make_pair
#define ff first
#define ss second
#define sz(a) (ll)(a).size()
#define sp(x) cout << fixed << setprecision(x);
#define ReadFile freopen("input.txt","r",stdin)
#define WriteFile freopen("output.txt","w",stdout)
#define endl "\n"

const ld pi = acos(-1);
const ll M=1e9+7,N=1e7+5,INF=1e18;

void solve()
{
    ll n,k,d,t;
    cin >> n >> k;
    vll a(n+1,0);

    f(i,1,k)
    {
        cin >> d;
        f(j,1,d)
        {
            cin >> t;
            a[t]++;
        }
    }

    t=0;
    f(i,1,n)
        if(!a[i])
            t++;
    
    cout << t << endl;
}

int32_t main()
{
    FIO
    solve();
    return 0;
}

Measured memory_bytes: 3652
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Main main = new Main();
		main.run();
	}

	public void run() {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int r[] = new int[9];
		for(int i=0; i<n; i++) {
			int v = sc.nextInt();
			if(v<400) {
				r[0]++;
			}else if(v<800) {
				r[1]++;
			}else if(v<1200) {
				r[2]++;
			}else if(v<1600) {
				r[3]++;
			}else if(v<2000) {
				r[4]++;
			}else if(v<2400) {
				r[5]++;
			}else if(v<2800) {
				r[6]++;
			}else if(v<3200) {
				r[7]++;
			}else {
				r[8]++;
			}
		}
		int min = 0;
		int max = 0;
		int s = 0;
		for(int i=0; i<8; i++) {
			if(r[i]>0) {
				min++;
			}else {
				s++;
			}
		}
		if(min==0) {
			min = 1;
			max = r[8];
		}else {
			max = min + r[8];
		}

		System.out.println(min+" "+max);
		sc.close();
	}
}


Measured memory_bytes: 38908
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int N; cin >> N;
    vector<int> A, B, C;
    A.reserve(N); B.reserve(N); C.reserve(N);
    rep(i, N) cin >> A[i];
    rep(i, N) cin >> B[i];
    rep(i, N-1) cin >> C[i];

    int ans = 0;
    rep(i, N) {
        ans += B[A[i]-1];
        if (i == 0) continue;
        if (A[i-1]+1 == A[i]) ans += C[A[i-1]-1];
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;

int main()
{
    int h, w;
    cin >> h >> w;
    vector<string> table(h);
    for (auto& v : table)
    {
        cin >> v;
    }

    set<int> rh, rw;
    for (int i = 0; i < h; i++)
    {
        int count = 0;
        for (int j = 0; j < w; j++)
        {
            if (table[i][j] == '#')
            {
                count++;
            }
        }
        if (count == 0)
        {
            rh.insert(i);
        }
    }
    for (int j = 0; j < w; j++)
    {
        int count = 0;
        for (int i = 0; i < h; i++)
        {
            if (table[i][j] == '#')
            {
                count++;
            }
        }
        if (count == 0)
        {
            rw.insert(j);
        }
    }

    for (int i = 0; i < h; i++)
    {
        if (rh.find(i) == rh.end())
        {
            for (int j = 0; j < w; j++)
            {
                if (rw.find(j) == rw.end())
                {
                    cout << table[i][j];
                }
            }
            cout << endl;
        }
    }
}


Measured memory_bytes: 256
#include<iostream>
#include<set>
#include<string.h>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
int n, a[100005], b[100005];
ll sum, tp;
signed main(){
    while (~scanf("%d", &n))
    {
    	sum = tp = 0;
    	for (int i = 1; i <= n; i++)	scanf("%d", &a[i]), sum += a[i];
    	for (int i = 2; i <= n; i += 2)
    	{
    		tp += a[i - 1] - a[i];
    		sum += tp * 2;
		}
		tp = 0;
		for (int i = n; i > 1; i -= 2)
    	{
    		tp += a[i] - a[i - 1];
    		sum += tp * 2;
		}
		b[1] = sum / n;
		for (int i = 2; i <= n; i++)
		{
			b[i] = a[i - 1] * 2 - b[i - 1];
		}
		for (int i = 1; i <= n; i++)
		{
			printf("%d%c", b[i], i == n ? '\n' : ' ');
		}
	}
}


Measured memory_bytes: 2048
#include <bits/stdc++.h>
#define fname "C"
#define bug(x) cerr << (#x) << " = " << (x) << endl
#define ll long long
#define REP0(i, n) for(int i = 0, _n = (n); i < _n; ++i)
#define REP1(i, n) for(int i = 1, _n = (n); i <= _n; ++i)
#define REPB0(i, n) for(int i = (n) - 1; i >= 0; --i)
#define REPB1(i, n) for(int i = (n); i > 0; --i)
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define FORB(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define ARR0(a, n) {cerr <<(#a)<< ": ["; REP0(i, n) cerr<< ' ' << a[i] <<','; cerr<<']'<<endl;}
#define ARR1(a, n) {cerr <<(#a)<< ": ["; REP1(i, n) cerr<< ' ' << a[i] <<','; cerr<<']'<<endl;}
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define LB lower_bound
#define UB upper_bound
#define X first
#define Y second

using namespace std;
template<typename T, typename V>
inline void bugp(const pair<T, V> &x) {cerr << '{' << x.X << ", " << x.Y << '}' << endl;}
template<typename T, typename U, typename V>
inline void bugpp(const pair<T, pair<U, V> > &x) {cerr << '{' << x.X << ", {" << x.Y.X << ", " << x.Y.Y << "}}" << endl;}
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ll, int> li;
typedef pair<ll, ii> lii;
typedef vector<int> vi;
typedef vector<vi> vvi;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0);
    ll x, k, d;
    cin >> x >> k >> d;
    ll m = min(abs(x/d), k);
    ll n = min(abs(x/d) + 1, k);
    if(abs(k - m) & 1) { // use n
        if(x > 0) x -= n*d;
        else x += n*d;
    }
    else { // use m
        if(x > 0) x -= m*d;
        else x += m*d;
    }
    cout << abs(x);
	return 0;
}


Measured memory_bytes: 3656
#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>;
const double PI = acos(-1);
const ll MOD = 1000000007;

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> p(N);
  rep(i, N) cin >> p[i];
  ll ans = 0;
  sort(p.begin(), p.end());
  rep(i, K) ans += p[i];
  cout << ans << endl;

}


Measured memory_bytes: 3628