akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;const int maxn = 2e6;int n ,p[maxn] ,w[maxn] ,m;
int dfs(int x){
    if(p[x]==x)return x;int q = p[x]; p[x] = dfs(q) , w[x]+= w[q];return p[x];
}
 main(){ios::sync_with_stdio(0) ,cin.tie(0) ,cout.tie(0);
   cin >> n >> m; for(int i=1;i<=n;i++)p[i]=i;
   while(m--){int l ,r ,d;   cin >> l >> r >> d;int x=dfs(l) ,y=dfs(r);if(x==y&&w[r]-w[l]!=d)return cout<<"No", 0;else p[y] = x ,w[y] = w[l]+d-w[r];}
   cout << "Yes";}


Measured memory_bytes: 4736
#include <bits/stdc++.h>
using namespace std;
 
void a(vector<set<int>> &B,vector<bool> &C,int k){
  if(C[k])
    return;
  C[k]=true;
  for(int i:B[k])
    a(B,C,i);
}

int main(){
  int N,M,l=0;
  cin>>N>>M;
  using pii=pair<int,int>;
  vector<pii> A(M);
  for(pii &i:A){
    int j,k;
    cin>>j>>k;
    i=make_pair(j-1,k-1);
  }
  for(pii &i:A){
    vector<set<int>> B(N);
    for(pii j:A){
      if((i.first!=j.first || i.second!=j.second)&&(i.first!=j.second || i.second!=j.first)){
        B[j.first].insert(j.second);
        B[j.second].insert(j.first);
      }
    }
    vector<bool> C(N,false);
    a(B,C,0);
    bool bo=true;
    for(bool b:C){
      bo=bo&&b;
    }
    if(!bo)
      l++;
  }
  cout<<l<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i = 0; i < (n); i++)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())
typedef long long ll;

int a[3], cnt[15];

int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
	FOR(i, 3) {
		cin >> a[i];
		cnt[a[i]]++;
	}
	cout << (cnt[5] == 2 && cnt[7] == 1 ? "YES" : "NO") << endl;
	return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <utility>
#include <deque>
#include <queue>
#include <functional>
#include <numeric>
using namespace std;

// bad knowhow
#define REP(i,n) for(long long i=0;i<(long long)n;++i)
#define ALL(x) (x).begin(), (x).end()

vector<int> g_taro;
vector<int> g_hana;

long long g_min_taro;
long long g_min_hana;

inline int getInt() { int s; scanf("%d", &s); return s; }


int main() {
	while (true) {
		g_taro.clear();
		g_hana.clear();
		g_min_hana = 100000;
		g_min_taro = 100000;

		int n,m;
		cin >> n >> m;
		if (n == 0) break;
		REP(i, n) g_taro.push_back(getInt());
		REP(i, m) g_hana.push_back(getInt());

		long long taro_sum = accumulate(ALL(g_taro), 0);
		long long hana_sum = accumulate(ALL(g_hana), 0);

		REP(i, n) REP(j, m) if (taro_sum - g_taro[i] + g_hana[j] == hana_sum - g_hana[j] + g_taro[i] && g_min_taro + g_min_hana > g_taro[i] + g_hana[j]) {
			g_min_taro = g_taro[i];
			g_min_hana = g_hana[j];
		}

		if (g_min_taro==100000) cout << -1 << endl;
		else cout << g_min_taro << " " << g_min_hana << endl;
	}
}

Measured memory_bytes: 1264
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pair;
const int inf = 1000000000; //10^9
const ll inff = 1000000000000000000; //10^18

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    int l = a*100 + b * 10 + c;
    if(l % 4 == 0) cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;
}

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

int main(){
    int N;
    cin >> N;
    vector<int> a;

    rep(i,N){
        int ai;
        cin >> ai;
        a.pb(ai);
    }
    // int x=0,y=0;
    // int xi=0,yi=a.size()-1;
    // while(xi<=yi){
    //     if(x<=y){
    //         x+=a[xi];
    //         xi++;
    //     }else{
    //         y+=a[yi];
    //         yi--;
    //     }
    //     if(x>=y){
    //         x = abs(x-y);
    //         y=0;
    //     }else{
    //         y = abs(x-y);
    //         x=0;
    //     }
    // }
    // cout << abs(x-y) << endl;

    long long int total=0;
    rep(i,N){
        total+=a[i];
    }
    long long int ans=LLONG_MAX;
    long long int byitotal=0;
    for(int i=0;i<N-1;i++){
        byitotal+=a[i];
        ans = min(abs((total-byitotal)-byitotal),ans);
    }
    cout << ans << endl;
    return 0;
}


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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl

typedef long long ll;

using namespace std;

const int INF = 1e9,MOD = 1e9 + 7,ohara = 1e6;
const ll LINF = 1e18;
long long int n,cnt=0,ans=0,a[ohara],b,c,d,cmp,cmpp,m,h,w,x,y,sum,pos;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

int main(void){
  
       cin.tie(0);
    ios::sync_with_stdio(false);
      
      cin>>n;
      map<ll,ll> mp;
      rep(i,n){
        cin>>a[i];
      }
      rrep(i,1,n){
        a[i]+=a[i-1];
      }
      rep(i,n){
        mp[a[i]]++;
        if(a[i]==0)ans++;
      }
      rep(i,n){
        pos=mp[a[i]];
        rrrep(j,pos-1,1)ans+=j;
        mp[a[i]]=0;
      }
      Cout(ans);
    
       
return 0;
}


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

int main()
{
    int k;
    cin >> k;
    string s;
    cin >> s;
    if(s.size() <= k)
    {
        cout << s;
        return 0;
    }
    for(int i =0; i < k ; i++)
        cout << s[i];
    cout << "...";


 return 0;
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ass 1e18
#define MOD 1000000007
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);
#define debug(x) cout << #x << ": " << x << endl;
#define debug2(x,y) cout<<#x<<": "<< x<< ", "<< #y<< ": "<< y<< endl;
#define debug3(x,y,z) cout<<#x<<": "<< x<< ", "<< #y<< ": "<< y<<" "<<#z<<" : "<<z<< endl;
using namespace std;
typedef long long int ll;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;   
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>

int main()
{
	boost
	ll cnt=0,n,i,a,b,c,maxi,mini;
	cin>>n;
	ll arr[n];
	for(i=0;i<n;i++)
		cin>>arr[i];
	for(i=1;i<=n-2;i++)
	{
		maxi=max(arr[i],max(arr[i-1],arr[i+1]));
		mini=min(arr[i],min(arr[i-1],arr[i+1]));
		if(arr[i]==maxi||arr[i]==mini)
			continue;
		cnt++;
	}
	cout<<cnt;
	return 0;
}

Measured memory_bytes: 256
from math import pi
from bisect import bisect_left as bl

def LIS(p) :
    route = []
    for y in p :
        pos = bl(route, y)
        if len(route) <= pos : route.append(y)
        else : route[pos] = y
    return len(route)


def main() :
    x1, y1, x2, y2 = map(int, input().split())
    xfilp = 1
    yflip = 1
    if x1 > x2 :
        xfilp = -1
        x1, x2 = x2, x1
    if y1 > y2 :
        yflip = -1
        y1, y2 = y2, y1
    n = int(input())
    p = []
    for i in range(n) :
        x, y = map(int, input().split())
        if x1 <= x <= x2 and y1 <= y <= y2 :
            p.append((x * xfilp, y * yflip))
    p = [y for x, y in sorted(p, key=lambda t:t[0])]
    foun = LIS(p)
    ans = 100*(x2-x1 + y2-y1) - (20 - pi*5)*foun
    if foun == min(x2-x1+1, y2-y1+1) :
        ans += pi*5
    print(ans)

main()

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

using namespace std;

int LargestRectangle(vector< int > height)
{
  stack< int > st;
  height.push_back(0);
  vector< int > left(height.size());
  int ret = 0;
  for(int i = 0; i < height.size(); i++) {
    while(!st.empty() && height[st.top()] >= height[i]) {
      ret = max(ret, (i - left[st.top()]) * height[st.top()]);
      st.pop();
    }
    left[i] = st.empty() ? -1 : st.top();
    st.emplace(i);
  }
  return (ret);
}

int main()
{
  int H, W;
  bool mat[2000][2000] = {{}};

  cin >> H >> W;
  for(int i = 0; i < H; i++) {
    string beet;
    cin >> beet;
    for(int j = 0; j < W; j++) mat[i][j] = beet[j] == '#';
  }

  for(int i = 0; i < H - 1; i++) {
    for(int j = 0; j < W - 1; j++) {
      mat[i][j] ^= mat[i + 1][j];
      mat[i][j] ^= mat[i + 1][j + 1];
      mat[i][j] ^= mat[i][j + 1];
    }
  }

  vector< int > height(W - 1, 1);
  int ret = max(H, W);
  for(int i = 0; i < H - 1; i++) {
    for(int j = 0; j < W - 1; j++) {
      if(mat[i][j]) height[j] = 1;
      else ++height[j];
    }
    ret = max(ret, LargestRectangle(height));
  }

  cout << ret << endl;
}



Measured memory_bytes: 4224
S = input()
T = input()

# 手順0
count = 0  # 予報が的中した回数

# 手順1: 1日目だけの話にもちこむ
forecast1 = S[0] # 1日目の天気予報
result1 = T[0]  #  1日目の実際の結果

if forecast1 == result1:
    count = count + 1

# 手順2: 2日目だけの話にもちこむ
forecast2 = S[1] # 2日目の天気予報
result2 = T[1] # 2日目の実際の結果

if forecast2 == result2:
    count = count + 1

# 手順3: 3日目の話
forecast3 = S[2]
result3 = T[2]

if forecast3 == result3:
    count = count + 1

print(count)


Measured memory_bytes: 9004
#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
int main(){
    int n;
    string s;
    cin>>n>>s;
    vector<int> v1(26,0);
    vector<int> v2(26,0);
    int max=0;
    for(int i=0;i<s.length();i++){
        v1.assign(26,0);
        v2.assign(26,0);
        
        for(int j=0;j<i;j++){
            v1[s[j]-'a']=1;
        }
        for(int k=i;k<s.length();k++){
            v2[s[k]-'a']=1;
        }
        int sum=0;
        for(int l=0;l<26;l++){
            sum+=v1[l]*v2[l];
            if(max<sum){
                max=sum;
            }
        }
    }
    cout<<max<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int arr[100003];
int dp[100003];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        
        cin>>arr[i];
    }
    dp[1]=0;
    dp[2]=abs(arr[2]-arr[1]);
for(int i=3;i<=n;i++){
    dp[i]=min(dp[i-2]+abs(arr[i]-arr[i-2]),dp[i-1]+abs(arr[i]-arr[i-1]));
}    
cout<<dp[n];
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>

template <int MOD>
struct ModInt {
    using lint = long long;
    using mint = ModInt<MOD>;

    int val;

    // constructor
    ModInt(lint v = 0) : val(v % MOD) {
        if (val < 0) val += MOD;
    };

    // assignment
    ModInt& operator=(const ModInt& x) {
        if (this != &x) { this->val = x.val; }
        return *this;
    }

    // unary operator
    ModInt operator+() const { return ModInt(val); }
    ModInt operator-() const { return ModInt(MOD - val); }
    ModInt operator~() const {
        // non-recursive extended euclidean algorithm
        int s = val, t = MOD;
        mint sx = 1, sy = 0, tx = 0, ty = 1;
        while (s % t != 0) {
            int div = s / t;
            s -= t * div;
            sx -= tx * div;
            sy -= ty * div;

            std::swap(s, t);
            std::swap(sx, tx);
            std::swap(sy, ty);
        }
        return mint(tx);
    }

    // arithmetic
    ModInt operator+(const ModInt& x) const { return ModInt(*this) += x; }
    ModInt operator-(const ModInt& x) const { return ModInt(*this) -= x; }
    ModInt operator*(const ModInt& x) const { return ModInt(*this) *= x; }
    ModInt operator/(const ModInt& x) const { return ModInt(*this) /= x; }

    // compound assignment
    ModInt& operator+=(const ModInt& x) {
        if ((val += x.val) >= MOD) val -= MOD;
        return *this;
    }
    ModInt& operator-=(const ModInt& x) {
        if ((val -= x.val) < 0) val += MOD;
        return *this;
    }
    ModInt& operator*=(const ModInt& x) {
        val = lint(val) * x.val % MOD;
        return *this;
    }
    ModInt& operator/=(const ModInt& x) { return *this *= ~x; }

    // compare
    bool operator==(const ModInt& b) const { return val == b.val; }
    bool operator!=(const ModInt& b) const { return val != b.val; }

    // I/O
    friend std::ostream& operator<<(std::ostream& os, const ModInt& x) noexcept { return os << x.val; }
};

constexpr int MOD = 1e9 + 7;
using mint = ModInt<MOD>;

int main() {
    int n;
    std::cin >> n;

    mint ans = 1;
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;

        if (x < cnt * 2 + 1) {
            ans *= (cnt + 1);
            --cnt;
        }
        ++cnt;
    }

    while (cnt > 0) {
        ans *= cnt;
        --cnt;
    }

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


Measured memory_bytes: 256
using System;

namespace HowManyDivisors
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			int[] data = getInputdata (" ");
			int count = 0;
			for (int i = data [0]; i <= data [1]; i++)
				if (data [2] % i == 0)
					count++;
			Console.WriteLine (count);

		}
		public static int[] getInputdata (string token)
		{
			string[] data = Console.ReadLine ().Split (token.ToCharArray ());
			int[] idata = new int[data.Length];

			for (int i = 0; i < data.Length; i++) {
				idata [i] = int.Parse (data [i]);
			}
			return idata;
		}


	}
}

Measured memory_bytes: 19924
#include<stdio.h>

int unbalanced(char* p){
    char a = *(p), b = *(p+1);
    if(a == *(p+2) || b == *(p+2)){
        return 1;
    }
    return 0;
}

int main(){
    char str[100001];
    scanf("%s", str);
    int a=0, flag = 1;
    if(str[2] == '\0' && str[0] == str[1]){
        flag = 0;
        printf("1 2");
    }
    while(str[a+2] != '\0'){
        if(unbalanced(&str[a]) == 1){
            flag = 0;
            printf("%d %d", a+1, a+3);
            break;
        }
        a++;
    }
    if(flag == 1){
        printf("-1 -1");
    }

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>


int main (void){
  
 long int a=0,b=0,max=0,n=0;
  scanf("%ld",&n);
  b=n;
 while(n>0)
 {
    a+=n%10;
    n/=10;
     
 }
 if(b%a==0)
 {
     printf("Yes");
 }else{
     printf("No");
 }
return 0;
    
}

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

using namespace std;

#define ll long long int

int main(void){
    string s,t;
    cin >> s >> t;

    int i;
    int ans=0;
    for(i=0;i<3;i++){
        if(s[i]==t[i]){
            ans++;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include <string>
#include<math.h>
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;
int main() {
    int a, b;
    cin >> a >> b;
    int M = a + b;
    M = max(M, a - b);
    M = max(M, a*b);
    cout << M << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
//#include <vector>
//#include <string>
//#include <algorithm>
//#include <math.h>
//#include <queue>
//#include <stack>
//#include <iomanip>

// sometimes used
//#include <set>
//#include <map>
//#include <numeric>
//#include <list>
//#include <deque>
//#include <unordered_map>

typedef long long LL;
//typedef long double LD;
using namespace std;
 
//#define MOD 1000000007
//#define MAX 200100
//#define NIL -1

int main() {
    LL a;
    LL b;
    LL c;
    LL k;
    LL ans;

    cin >> a >> b >> c >> k;
    if(a>k){
        ans=k;
    }else if(a+b>k){
        ans=a;
    }else{
        //cout << "test" << endl;
        //cout << a << " " << k-a-b << endl;
        ans=a-(k-a-b);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3596
N=int(input())
f=True
s=set()
last=input();s.add(last)
for i in range(N-1):
    w=input()
    if w in s or last[-1]!=w[0]:
        f=False
        break
    else:
        s.add(w)
        last=w
print('Yes' if f else 'No')

Measured memory_bytes: 38384
#include <iostream>
#include <queue>
using namespace std;
int h,w,c;
int dis[10][10];
int ans;
int count;
struct po{
  int mp[10][10];
};

struct xy{
  int x,y;
};

void deb(po t) {
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++)
      cout << t.mp[i][j] << " ";
    cout << endl;
  }
  cout <<"-----------------"<<endl;

}


void saiki(po sta,int d){
  // for(int i=0;i<6;i++) cout <<sta.flg[i];
  //cout << endl;
  count++;
  po t = sta;
  if(d <= 6 ) {
    for(int i=0;i<6;i++){
      if(t.mp[0][0] != i+1) {
	if(d == 5 && i != c-1) continue;
	queue <xy> Q;
	Q.push((xy){0,0});
	for(int j=0;j<h;j++) for(int k=0;k<w;k++) dis[j][k] = 0;
	dis[0][0] = 1;
	int tf = 0;
	int sum = 1;
	while(!Q.empty()){
	  int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};
	  xy u = Q.front();
	  Q.pop();
	  for(int j=0;j<4;j++) {
	    int tx = u.x+dx[j] , ty = u.y+dy[j];
	    if(tx>=0 && tx<w && ty>=0 && ty<h){
	      if(t.mp[ty][tx]==t.mp[0][0] && dis[ty][tx]==0) {
		Q.push((xy){tx,ty});
		dis[ty][tx] = 1;
		sum++;
	      }
	      if(t.mp[ty][tx]==i+1 && d!=6) tf = 1;
	    }
	  }
	}
	po tmp = t;
	if(tf == 1 && d != 6) {
	  for(int j=0;j<h;j++)
	    for(int k=0;k<w;k++)
	      if(dis[j][k] == 1) t.mp[j][k] = i+1;
	}
	else if(d != 6) t.mp[0][0] = i+1;

	if(t.mp[0][0] == c && d!=6) saiki(t,6); 
	if(sum > ans && t.mp[0][0] == c )   ans = sum;
	      
	saiki(t,d+1);
	t = tmp;
      }
    }
  }
}   



int main() {

  while(1) {

    cin >> h >> w  >> c;
    if(h == 0 && w == 0 && c == 0) break;
    
    po in;
    for(int i=0;i<h;i++)
      for(int j=0;j<w;j++)
	cin >> in.mp[i][j];
    
    ans = 0;
    saiki(in,1);

    cout << ans << endl;   
    //cout <<count << endl;

  }    


  return 0;

}

Measured memory_bytes: 1212
# encoding:utf-8
import copy
import numpy as np
import random
import bisect #
import math

ans = 0
menu_time = []
for i in range(5):
    menu_time.append(int(input()))

amari = 10
for i in range(5):
    if menu_time[i]%10>0:
        amari = min(menu_time[i]%10,amari)
    ans += math.ceil(menu_time[i]/10)*10

ans -= 10
ans += amari


print(ans)


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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n; cin>>n;
    ll a,b,c,d,e; cin >> a >>b >>c>>d>>e;
    ll m = min(min(min(min(a,b),c),d),e);
    ll ans = n / m;
    if(n%m!=0) ans++;
    cout << ans+4 << endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

"""
コンテスト後に解説記事を見てAC
Python 3だとTLE
"""

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

def solve(N_str):
    """
    https://betrue12.hateblo.jp/ の通り実装

    上の桁から順番に見ていく
    dp[i][j] =
      上から i 桁目までの硬貨の支払いとお釣りを処理し終わって、
      N の i 桁目までの金額よりも j 枚分多く支払っているときの、
      これまでの支払い・お釣り硬貨の最小合計枚数
    """
    N_str = '0' + N_str
    dp = [[0] * 2 for _ in range(len(N_str))]

    # 0376円のとき

    # dp[1][0] = 0       0円払う(0)
    # dp[1][1] = 1    1000円払う(1)
    #
    # dp[2][0] = 3    0円の状態から300円払う(3)  vs  1000円の状態から700円お釣りをもらう(8)
    # dp[2][1] = 4    0円の状態から400円払う(4)  vs  1000円の状態から600円お釣りをもらう(7)
    #
    # dp[3][0] = 7    300円の状態から追加で70円払う(3+7) vs 400円の状態から30円もらう(4+3)
    # dp[3][1] = 6    300円の状態から追加で80円払う(3+8) vs 400円の状態から20円もらう(4+2)
    #
    # dp[4][0] = 10   370円の状態から追加で6円払う(7+6) vs 380円の状態から4円もらう(6+4)
    # dp[4][1] = 9    370円の状態から追加で7円払う(7+7) vs 380円の状態から3円もらう(6+3)

    for i, ch in enumerate(N_str):
        if i == 0:
            dp[0][0] = 0
            dp[0][1] = 1
        else:
            dp[i][0] = min(dp[i - 1][0] + int(ch),
                           dp[i - 1][1] + 10 - int(ch))
            dp[i][1] = min(dp[i - 1][0] + int(ch) + 1,
                           dp[i - 1][1] + 9 - int(ch))

    return dp[len(N_str) - 1][0]


def wrong(N_str):
    """最初に間違って書いた貪欲
    1の位から見ていき、0~4なら支払い、5~9なら10払ってお釣りをもらう

    N = 65のとき、
    この関数だと70払って5お釣りをもらうことになるが
    実際は100払って35お釣りをもらうべきなので誤り
    """
    N_str = N_str[::-1]
    ans = 0
    prev = 0
    for ch in N_str:
        n = int(ch)
        n += prev
        if n <= 5:
            ans += n
            prev = 0
        else:
            ans += 10 - n
            prev = 1
    ans += prev    
    return ans

# for n in range(1, 101):
#     print()
#     n_str = str(n)
#     w = wrong(n_str)
#     gt = solve(n_str)
#     if w != gt:
#         print("n, gt, wrong = ", n, gt, w)

N_str = input()
print(solve(N_str))


Measured memory_bytes: 140552
#include <iostream>
#include <algorithm>

#define MAX_NM 1000

int n, m, ans;
int p[MAX_NM];

void solve();

int main(){
    while(true){
        std::cin >> n >> m;
        if(n == 0 && m == 0)
            break;
        for(int i = 0; i < n; ++i)
            std::cin >> p[i];
        solve();
        std::cout << ans << std::endl;
    }
    return 0;
}

void solve(){
    ans = 0;
    std::sort(p, p + n, std::greater<int>());
    for(int i = 1; i <= n; ++i){
        if(i % m == 0)
            continue;
        ans += p[i - 1];
    }
    return;
}

Measured memory_bytes: 1180
k,n = map(int,input().split())

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

start = 0
max_sa = 0
for i in range(n):
	if i+1 == n:
		sa = a[(i+1)%n] - (a[i%n]-k)
	else:
		sa = a[(i+1)%n] - a[i%n]

	if max_sa < sa:
		max_sa = sa
		start = (i+1)%n

ans = 0
for i in range(n-1):
	if start+i+1 == n:
		ans += a[(start+i+1)%n] - (a[(start+i)%n]-k)
	else:
		ans += a[(start+i+1)%n] - a[(start+i)%n]

print(ans)


Measured memory_bytes: 26444
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
#define rep(i, a, n) for (ll i = (a); i < (n); i++)
#define debug(x) cerr << #x << ": " << x << endl;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

int main() {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;

    ll e = c * d / __gcd(c, d);
    ll cnta = a-1 - (a-1) / c - (a-1) / d + (a-1) / e;
    ll cntb = b - b / c - b / d + b / e;
    cout << cntb - cnta << endl;
}

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

typedef long long LL;
const int mod = 1e9 + 7;
const int MAXN = 45, MAXS = 2e6 + 5; 

template<typename _T>
void read( _T &x )
{
	x = 0;char s = getchar();int f = 1;
	while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
	while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
	x *= f;
}

template<typename _T>
void write( _T x )
{
	if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
	if( 9 < x ){ write( x / 10 ); }
	putchar( x % 10 + '0' );
}

map<LL, int> state;

int f[MAXN][MAXS];
int trans[MAXS][11];
int seq[MAXN], siz;
int cnt = 0;
int N, X, Y, Z;
bool legal[MAXS];

void add( int &x, const int v ) { x = ( x + v >= mod ? x + v - mod : x + v ); }

void DFS( const int su, const LL H )
{
	if( su > X + Y + Z ) return ;
	state[H] = ++ cnt;
	for( int i = 1 ; i <= 10 ; i ++ )
		DFS( su + i, H * 10 + i ); 
}

bool chk()
{
	int s[MAXN] = {};
	for( int i = 1 ; i <= siz ; i ++ ) s[i] = s[i - 1] + seq[i];
	bool flag = false;
	for( int i = 1 ; i <= siz ; i ++ )
		if( s[i] == X )
		{ flag = true; break; }
	if( ! flag ) return false;
	flag = false;
	for( int i = 1 ; i <= siz ; i ++ )
		if( s[i] == X + Y )
		{ flag = true; break; }
	if( ! flag ) return false;
	return s[siz] == X + Y + Z;
}

int push( const int c )
{
	int su = 0, l;
	for( l = siz ; l ; su += seq[l --] )
		if( c + su + seq[l] > X + Y + Z )
			break;
	LL val = 0;
	for( int j = l + 1 ; j <= siz ; j ++ )
		val = val * 10 + seq[j];
	if( c <= X + Y + Z ) val = val * 10 + c;
	return state[val];
}

void init( const int su )
{
	if( su > X + Y + Z ) return ;
	legal[++ cnt] = chk();
	for( int i = 1 ; i <= 10 ; i ++ ) trans[cnt][i] = push( i );
	for( int c = 1 ; c <= 10 ; c ++ )
		seq[++ siz] = c, init( su + c ), siz --;
}

int main()
{
	read( N ), read( X ), read( Y ), read( Z );
	DFS( 0, 0 ); 
	cnt = 0; init( 0 );
	
	f[0][1] = 1;
	for( int i = 0 ; i < N ; i ++ )
		for( int k = 1 ; k <= cnt ; k ++ )
			if( f[i][k] && ! legal[k] )
				for( int c = 1 ; c <= 10 ; c ++ )
					if( trans[k][c] && ! legal[trans[k][c]] )
						add( f[i + 1][trans[k][c]], f[i][k] );
	int ans = 1;
	for( int i = 1 ; i <= N ; i ++ )
		ans = 10ll * ans % mod;
	for( int i = 1 ; i <= cnt ; i ++ )
		if( ! legal[i] )
			add( ans, mod - f[N][i] );	
	write( ans ), putchar( '\n' );
	return 0;
}

Measured memory_bytes: 36240
package main

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

var sc = bufio.NewScanner(os.Stdin)

func contains(target string, list []string) bool {
	for _, r := range list {
		if target == r {
			return true
		}
	}
	return false
}

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

func nextInt() int {
	sc.Scan()

	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func nextF64() float64 {
	sc.Scan()

	i, e := strconv.ParseFloat(sc.Text(), 64)
	if e != nil {
		panic(e)
	}
	return i
}

func isInteger(x float64) bool {
	return math.Floor(x) == x
}

func Ave(s []int) int {
	val := 0
	for _, i := range s {
		val += i
	}
	return int(val / len(s))
}
func cal(i int) (sum int) {
	for i != 0 {
		sum += i % 10
		i /= 10
	}
	return
}
func max(a []int) (idx int, val int) {
	max := a[0]
	idx = 0
	for j, i := range a {
		if max < i {
			max = i
			idx = j
		}
	}
	return idx, max
}

func draw(i int, a []int) (l []int) {
	// p = a[i]
	for j := i; j < len(a); j++ {
		if j != len(a)-1 {
			a[j] = a[j+1]
		} else if j == len(a)-1 {
			a = a[:len(a)-1]
		}
	}
	return a
}

func main() {
	sc.Split(bufio.ScanWords)
	// sc.Buffer([]byte{}, math.MaxInt64)
	// a := make([][]int, 3)
	// for i := 0; i < 3; i++ {
	// 	a[i] = make([]int, 3)
	// }
	// for i := 0; i < 3; i++ {
	// 	for j := 0; j < 3; j++ {
	// 		a[i][j] = nextInt()
	// 	}
	// }

	n := nextInt()

	var out int
	var ans int

	for i := 1; i <= n; i++ {
		if i%2 == 0 {
			cnt := 0
			for j := i; j%2 == 0; {
				j = j / 2
				cnt++
			}
			if cnt > out {
				out = cnt
				ans = i
			}
		} else if i == 1 {
			ans = 1
		}

	}

	fmt.Println(ans)

}


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

long long dp[105][100005];

int main(){
    int n,w; cin>>n>>w;
    vector<int> a(n),v(n);
    for(int i=0;i<n;i++){
        cin>>a[i]>>v[i];
    }
    for(int i=0;i<=100000;i++) dp[0][i]=1e10;
    dp[0][0]=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<=100000;j++){
            if(j<v[i]) dp[i+1][j]=dp[i][j];
            else dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+a[i]);
        }
    }
    int ans=0;
    for(int i=0;i<=100000;i++){
        if(dp[n][i]<=w) ans=i;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 80256
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<int> VI;
typedef vector<VI> VVI;
const double EPS = 1e-12;
const int INF = numeric_limits<int>::max() / 2;
const int NEG_INF = numeric_limits<int>::min() / 2;
const int MOD = 1e9 + 7;

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

    int n;cin>>n;
    vector<vector<int>> a(2,vector<int>(n+1));
    for(int i=0;i<2;i++){
        for(int j=1;j<=n;j++) cin>>a[i][j];
    }
    vector<vector<int>> sum(2,vector<int>(n+1,0));
    for(int i=1;i<=n;i++){
        sum[0][i]=sum[0][i-1]+a[0][i];
        sum[1][i]=sum[1][i-1]+a[1][i];
    }
    int res=0;
    for(int i=1;i<=n;i++){
        res=max(res,sum[0][i]+sum[1][n]-sum[1][i-1]);
    }
    cout<<res<<endl;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
        int b;
        cin>>b;
                if(b==999){
                    cout<<"111";
        }
                if(b==991){
                    cout<<"119";
        }
                if(b==919){
                    cout<<"191";
        }
                if(b==199){
                    cout<<"911";
        }
                if(b==911){
                    cout<<"199";
        }
                if(b==191){
                    cout<<"919";
        }
                if(b==119){
                    cout<<"991";
        }
                if(b==111){
                    cout<<"999";
        }
    }


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a=n/100;
    int b=n%100/10;
    int c=n%10;
    if(a>b||(a==b&&a>c)) printf("%d",a*100+a*10+a);
    else if(a<b||(a==b && a<c)) printf("%d",(a+1)*100+(a+1)*10+(a+1));
    else if(a==b&& a==c) printf("%d",n);
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
constexpr double PI = 3.1415926535897932;   // acos(-1)
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

using ld = double;
int n;
ld dp[305][305][305];
bool used[305][305][305];

ld memo_rec(int One, int Two, int Three){
    if(used[One][Two][Three])   return dp[One][Two][Three];
    if(One + Two + Three == 0){
        used[One][Two][Three] = true;
        return dp[One][Two][Three] = 0.0;
    }
    
    ld res = n;
    if(One > 0) res += memo_rec(One - 1, Two, Three) * One;
    if(Two > 0) res += memo_rec(One + 1, Two - 1, Three) * Two;
    if(Three > 0)   res += memo_rec(One, Two + 1, Three - 1) * Three;
    res *= 1.0 / (One + Two + Three);

    used[One][Two][Three] = true;
    return dp[One][Two][Three] = res;
}

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

    cin >> n;
    vector<int> cnt(4, 0);
    for(int i = 0; i < n; ++i){
        int a;
        cin >> a;
        ++cnt[a];
    }
    
    cout << fixed << setprecision(15);
    cout << memo_rec(cnt[1], cnt[2], cnt[3]) << endl;
}

Measured memory_bytes: 246016
/*                         _
                        _ooOoo_
                       o8888888o
                       88" . "88
                       (| -_- |)
                       O\  =  /O
                    ____/`---'\____
                  .'  \\|     |//  `.
                 /  \\|||  :  |||//  \
                /  _||||| -:- |||||_  \
                |   | \\\  -  /'| |   |
                | \_|  `\`---'//  |_/ |
                \  .-\__ `-. -'__/-.  /
              ___`. .'  /--.--\  `. .'___
           ."" '<  `.___\_<|>_/___.' _> \"".
          | | :  `- \`. ;`. _/; .'/ /  .' ; |
          \  \ `-.   \_\_`. _.'_/_/  -' _.' /
===========`-.`___`-.__\ \___  /__.-'_.'_.-'================

                  Please give me AC.
*/

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>

using namespace std;

using int64 = long long;
using uint64 = unsigned long long;
using vi = vector<int>;
using vl = vector<int64>;
using pii = pair<int, int>;
using pll = pair<int64, int64>;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define print(x) cout << (x) << '\n'
#define print2(x, y) cout << (x) << ' ' << (y) << '\n'
#define print3(x, y, z) cout << (x) << ' ' << (y) << ' ' << (z) << '\n'
#define printn(v) rep(i, (v).size() - 1) cout << (v)[i] << ' '; cout << (v)[n - 1] << '\n';
#define debug(x) cerr << #x << ": " << (x) << '\n'
#define debug2(x, y) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v) for (size_t _ = 0; _ < v.size(); ++_){cerr << #v << "[" << _ << "] : " << v[_] << '\n';}
// constant
const int INF = (1<<30) - 1;
const int64 INF64 = (1LL<<62) - 1;

// End of template.


int main(){
    cout << fixed << setprecision(15);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    bool flag = true;
    for (int i = 0; i < s.length(); i += 2) {
        if (s[i] == 'L') flag = false;
    }

    for (int i = 1; i < s.length(); i += 2) {
        if (s[i] == 'R') flag = false;
    }

    print(flag ? "Yes" : "No");

    return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
int main(void) {
    int n,i;
    int a[3];
    scanf("%d",&n);
    a[0]=(n/100);
    a[1]=(n%100)/10;
    a[2]=(n%100)-10*a[1];
    for (i=0;i<3;i++) {
        if (a[i]==1) {
            a[i]=9;
        } else {
            a[i]=1;
        }
    }
    printf("%d\n",a[0]*100+a[1]*10+a[2]*1);
    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
#include<complex>
#include<set>
using namespace std;
typedef long long int llint;
#define rep(i,n) for(int i=0;i<n;i++)
int main() {
	int n, k;
	cin >> n >> k;
	vector<int>a(n);
	int ans = 0;
	rep(i, n) {
		cin >> a[i];
		ans += a[i];
	}
	sort(a.begin(), a.end());
	rep(i, n - k) {
		ans -= a[i];
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define IOSF ios::sync_with_stdio(false)
typedef long long LL;
using namespace std;
const int INF=0x3f3f3f3f;
//const int MAX=10e5+5;

int math[20];


int main() {
    IOSF;
    cin>>math[0]>>math[1]>>math[2];
    sort(math,math+3);
    int sum=0;
    if((math[1]-math[0])%2==0){
        int temp=math[2]-math[1];
        sum+=temp;
        sum=sum+(math[2]-math[0]-temp)/2;
        cout<<sum<<endl;
    }
    else{
        int temp=math[2]-math[1];
        sum=temp+1;
        sum=sum+(math[2]-math[0]-temp+1)/2;
        cout<<sum<<endl;
    }
    return 0;
}





Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	string s; cin >> s;
	for(int i = 0; i < s.size(); i++){
		cout << (char)((s[i] - 'A' + n) % 26 + 'A');
	}
}


Measured memory_bytes: 3664
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0;i < (n);i++)
using ll = long long;
const ll MOD=1000000007;
const double pi=acos(-1);


int N,M,Q;
vector<vector<int>> A(0);

void make(vector<int> a,int n)
{
  if(n==N) {A.push_back(a); return;}
  if(n==0)
  {
    rep(i,M)
    {
      make({i+1},1);
    }
    return;
  }
  int l=a.at(n-1);
  for(int i=l;i<=M;i++)
  {
    auto b=a;
    b.push_back(i);
    make(b,n+1);
  }
}  



int main() 
{
  cin>>N>>M>>Q;
  make({},0);
  /*
  for(auto a:A)
  {
    for(auto w:a)
    {
      cout<<w<<" ";
    }
    cout<<endl;
  }
  */
  
  vector<int> a(Q);
  vector<int> b(Q);
  vector<int> c(Q);
  vector<int> d(Q);
  rep(i,Q)
  {
    cin>>a.at(i)>>b.at(i)>>c.at(i)>>d.at(i);
    a.at(i)--;
    b.at(i)--;
  }
  
  int ans=0;
  for(auto hoge:A)
  {
    int sum=0;
    rep(i,Q)
    {
      if(hoge.at(b.at(i))-hoge.at(a.at(i))==c.at(i))
      {
        sum+=d.at(i);
      }
    }
    ans=max(sum,ans);
  }
  
  cout<<ans<<endl;
  
  return 0;
}



Measured memory_bytes: 13532
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<numeric>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
typedef vector<int> vec;

int main(){
    int N;cin>>N;
    int C[510],S[510],F[510];
    for(int i=1;i<N;i++)
        cin>>C[i]>>S[i]>>F[i];
    
    vec time(510,0);
    for(int i=1;i<=N;i++){
        for(int j=i;j<N;j++){
            if(time[i]<S[j])time[i]=S[j]+C[j];
            else{
                if(time[i]%F[j]!=0)
                    time[i]+=F[j]-time[i]%F[j];
                time[i]+=C[j];
            }
        }
        cout<<time[i]<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
H,W=list(map(int,input().split()))

S=[]
for i in range(H):
    s=input()
    S.append(s)

for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            if i == 0 and j == 0:
                if S[0][1] == "." and S[1][0] == ".":
                    print("No")
                    exit()
            elif i == 0 and j == W-1:
                if S[0][W-2] == "." and S[1][W-1] == ".":
                    print("No")
                    exit()
            elif i == H-1 and j == 0:
                if S[H-1][1] == "." and S[H-2][0] == ".":
                    print("No")
                    exit()
            elif i == H-1 and j == W-1:
                if S[H-1][W-2] == "." and S[H-2][W-1] == ".":
                    print("No")
                    exit()
            elif i == 0 and j >= 1:
                if S[i][j-1] == "." and S[i][j+1] == "." and S[i+1][j] == ".":
                    print("No")
                    exit()
            elif i == H-1 and j >=1:
                if S[i][j-1] == "." and S[i][j+1] == "." and S[i-1][j] == ".":
                    print("No")
                    exit()
            elif i >= 1 and j == 0:
                if S[i][j+1] == "." and S[i-1][j] == "." and S[i+1][j] == ".":
                    print("No")
                    exit()
            elif i >= 1 and j == W-1:
                if S[i][j-1] == "." and S[i-1][j] == "." and S[i+1][j] == ".":
                    print("No")
                    exit()
            elif i >=1 and j >= 1:
                if S[i][j-1] == "." and S[i][j+1] == "." and S[i-1][j] == "." and S[i+1][j] == ".":
                    print("No")
                    exit()
print("Yes")


Measured memory_bytes: 3192
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        LinkedList<String> ans = new LinkedList<>();

        for (int i = 0; i < s.length(); i++) {
            switch (s.charAt(i)) {
                case '0':
                    ans.add("0");
                    break;
                case '1':
                    ans.add("1");
                    break;
                case 'B':
                    if (!ans.isEmpty()) {
                        ans.removeLast();
                    }
                    break;
            }
        }

        for (String val: ans) {
            System.out.print(val);
        }
    }
}


Measured memory_bytes: 22996
import sys
from collections import deque
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N, M = map(int, readline().split())
 
G = [[] for _ in range(N + 1)]
m = map(int, read().split())
for a, b in zip(m, m):
    G[a].append(b)
    G[b].append(a)
 
par = [0] * (N + 1)
visited = [0] * (N + 1)
root = 1
visited[root] = 1
q = deque([root])
while q:
    v = q.popleft()
    for w in G[v]:
        if visited[w]:
            continue
        visited[w] = 1
        par[w] = v
        q.append(w)
 
print('Yes')
print(*par[2:], sep='\n')

Measured memory_bytes: 54516
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define int long long
constexpr long long INF = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
using Graph = vector<vector<int>>;

using mint=modint998244353;

struct S{
    mint a;
    int size;
};

struct F{
    mint a,b;
};

S op(S l,S r){
    return S{l.a+r.a,l.size+r.size};
}

S e(){
    return S{0,0};
}

S mapping(F l,S r){
    return S{r.a*l.a+r.size*l.b,r.size};
}

F composition(F l,F r){
    return F{r.a*l.a,r.b*l.a+l.b};
}
F id(){
    return F{1,0};
}



signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int N,Q;
    cin>>N>>Q;


    vector<S> a(N);
    rep(i,N){
        int x;
        cin>>x;
        a[i]=S{x,1};
    }

    lazy_segtree<S,op,e,F,mapping,composition,id> seg(a);

    rep(i,Q){
        int t;
        cin>>t;
        if(t){
            int l,r;
            cin>>l>>r;
            cout<<seg.prod(l,r).a.val()<<endl;
        }else{
            int l,r,b,c;
            cin>>l>>r>>b>>c;
            seg.apply(l,r,F{b,c});
        }
    }
    



}


Measured memory_bytes: 31468
import sys

# 関数 solve は，もちろん，問題に応じて書き換える
def solve(N):
    hantei = 0
    for i in range(26):
        for j in range(20):
            if 4*i + 7*j == N :
                hantei = 4*i + 7*j
    if hantei == N :
        return ('Yes')
    else :
        return('No')
# ここから下は，入力・出力形式が同じであれば，変えなくて良い．
def readQuestion():
    line = sys.stdin.readline().rstrip()
    return int(line)

def main():
    n = readQuestion()
    answer = solve(n)
    print(answer)
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
#include <iostream>
#include <stdio.h>
#include <cstring>
#define N 200005
using namespace std;
char s[N], t[N];
int n, i, ans;
int main(){
	scanf("%s\n%s", s, t);
	n=strlen(s);
	for(i=0; i<n; i++){
		if(s[i]!=t[i]) ans++;
	}
	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 4144
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i=0;i < (int)(n);i++)

int main(){
   int k;
   string s;
   cin >> k >> s;
   if (s.size() <= k){
      cout << s << endl;
      return 0;
   }
   else{
      string tmp;
      tmp = s.substr(0,k)+"...";
      cout << tmp << endl;
   }
   return 0;
}


Measured memory_bytes: 3596
N, Q = map(int, input().split())
S = input()
A = [0, 0]

for i in range(1, N):
	if S[i - 1] == 'A' and S[i] == 'C':
		A.append(A[i] + 1)
	else:
		A.append(A[i])
		
for i in range(Q):
	l, r = map(int, input().split())
	print(A[r] - A[l])


Measured memory_bytes: 6096
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    s = input().rstrip()
    alphabet = 'abcdefghijklmnopqrstuvwxyz' #26
    if s[0] == 'A':
        cnt = 0
        for i in range(len(s)):
            if 2<=i<=len(s)-2:
                if s[i] == 'C':
                    cnt += 1
                    k = i
        if cnt == 1:
            for i in range(len(s)):
                if i==0 or i==k:
                    continue
                else:
                    if s[i] not in alphabet:
                        break
            else:
                print('AC')
                exit()
    print('WA')

if __name__ == '__main__':
    main()

Measured memory_bytes: 3316
MOD = 10**9 + 7
MAX = int(2e5)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


FACT = [1] * (MAX+1)
for i in range(1, MAX+1):
    FACT[i] = (i * FACT[i-1]) % MOD
INV = [1] * (MAX+1)
INV[MAX] = div(1, FACT[MAX])
for i in range(MAX, 0, -1):
    INV[i-1] = (INV[i] * i) % MOD


def main():
    n, k = map(int, input().split())
    ans = 0
    for i in range(min(n-1, k)+1):
        # iCn
        # (n-i-1)C(n-1)
        tmp = FACT[n] * INV[i] * INV[n-i] % MOD
        tmp = (tmp * FACT[n-1] * INV[n-i-1] * INV[i]) % MOD
        ans = (ans + tmp) % MOD
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 44012
from itertools import combinations

n, m, q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(q)]

ret = 0
for a in combinations(list(range(1, n + m)), n):
    a = sorted(a)
    a = [a - i for i, a in enumerate(a)]
    pret = 0
    for i in range(q):
        ai, bi, ci, di = abcd[i]
        if a[bi - 1] - a[ai - 1] == ci:
            pret += di
    ret = max(ret, pret)
print(ret)


Measured memory_bytes: 9204
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  int ans=0;
  cin >> N;
  vector<int> vec(N);
  
  for(int i=0;i<N;i++){
    cin >> vec.at(i);   
  }
 
  vector<int> check;
  check={};
  int k = 1;
  
  for(int i =0;i<N;i++){
    
    ans += 1;
    
      if(vec.at(k-1)==2){
        break;
      }

    k = vec.at(k-1);
    if(i == N-1){
        ans =-1;
    }
  }
  
  
  cout << ans << endl;
  return 0;
}

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

ret = 0
for i in range(1, N):
    cnt = max(0, A[i] + A[i - 1] - x)

    ret += cnt
    A[i] = max(0, A[i] - cnt)

print(ret)


Measured memory_bytes: 14052
#include <bits/stdc++.h>
using namespace std;
int H, W; string s;
int main() {
	cin >> H >> W;
	cout << string(W + 2, '#') << endl;
	for(int i = 0; i < H; i++) cin >> s, cout << '#' << s << '#' << endl;
	cout << string(W + 2, '#') << endl;
	return 0;
}

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

#define int long long int
#define vi vector<int>
#define vvi vector<vi>
#define read(a)  for(int i = 0; i < n; i++) cin >> a[i];
#define print(a)  for(int i = 0; i < n; i++) cout << a[i] << " ";
#define pb push_back
#define ins insert
#define pql priority_queue<int>
#define pqs priority_queue<int, vi, greater<int>>
#define pqlv priority_queue<vi>
#define pqsv priority_queue<vi, vvi, greater<vi>>
#define endl '\n'

signed main() {
    string s, t;
    cin >> s >> t;
    if(t.size() - s.size() != 1) {
        cout << "No";
        return 0;
    }
    for(int i = 0; i < s.size(); i++) {
        if(s[i] != t[i]) {
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
}

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

using namespace std;

const int INF = 1e9 + 7;
const int N = (int)2e5 + 3;

typedef long long ll;
typedef long double ld;

typedef pair < ll, ll > pll;
typedef pair < int, int > pii;

int n, pos;
int main(){
  scanf ("%d %d", &n, &pos);
  int x = pos, timer = 0;
  for (int i = n; i >= 1; --i){
    timer++;
    if (i == x){
      break;
    }
  }
  printf ("%d\n", timer);
  return 0;
}


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

using namespace std;
using llong = long long;
using P = pair<llong, llong>;

#define BE(x) x.begin(), x.end()

const llong inf = llong(1e18)+7;
const llong mod = 1e9+7;

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

	if(abs(x-a) > abs(x-b))
		cout << 'B' << endl;
	else
		cout << "A" << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<bits/stdc++.h>
#define int long long
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int32_t main()
{
int n,k;
cin>>n>>k;
	map<int,int>mp;
while(k--)
{
	int d;
	cin>>d;
	int x;

	for(int i=0;i<d;i++)
	{  cin>>x;
		mp[x]+=1;
	}
}
int count=0;
map<int,int> :: iterator itr;
for(itr=mp.begin();itr!=mp.end();itr++)
{
	if(itr->second>=1)
	{
		count++;
	}
}
cout<<n-count;
}


Measured memory_bytes: 3632
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    int[] A = new int[N];
    int[] B = new int[N];
    for (int i = 0; i < N; i++) {
      A[i] = sc.nextInt();
      B[i] = sc.nextInt();
    }
    Main abc122C = new Main();
    System.out.println(abc122C.solve(N, M, A, B));
  }
 
  public long solve(int N, int M, int[] A, int[] B) {
    long ans = 0;
    Store[] Stores = new Store[N];
    for (int i = 0; i < N; i++) {
      Stores[i] = new Store(A[i], B[i]);
    }
    Arrays.sort(Stores);
    for (int i = 0; i < N; i++) {
      int num = M > Stores[i].num ? Stores[i].num : M;
      ans += (long) num * Stores[i].price;
      M -= num;
      if(M == 0) break;
    }
    return ans;
  }
 
  class Store implements Comparable<Store> {
    int price;
    int num;
    public Store(int price, int num){
      this.price = price;
      this.num = num;
    }
    @Override
    public int compareTo(Store other) {
      return this.price - other.price;
    }
  }
}

Measured memory_bytes: 91444