QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#135416 | #6310. Dining Professors | Spinoza | AC ✓ | 26ms | 17276kb | C++20 | 8.5kb | 2023-08-05 14:59:23 | 2023-08-05 14:59:26 |
Judging History
answer
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<climits>
#include<cctype>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using vl=vector<ll>;
using vc=vector<char>;
using vvl=vector<vl>;
using vvc=vector<vc>;
using pll=pair<ll,ll>;
using mll=map<ll,ll>;
using sl=set<ll>;
using ql=queue<ll>;
using pql=priority_queue<ll> ;
using stl=stack<ll>;
constexpr double eps=1e-10;
constexpr ll inf=1e18;
constexpr ll N=1<<20;
constexpr ll P=1e9+7;
constexpr ll inv2=(P+1)/2;
#define pb(x) push_back(x)
#define forfront(i,x,y) for (ll i = (x) ; i <= (y) ; ++i)
#define forback(i,x,y) for (ll i = (x) ; i >=(y) ; --i )
#define add(a,b) ( a + b >= P ? a + b - P : a + b )
#define dec(a,b) ( a < b ? a - b + P : a - b )
#define sz(v) ( (ll) v . size ( ) )
#define all(v) (v).begin (), (v).end ()
#define one(x) memset (x , -1 , sz (x) )
#define zero(x) memset ( x, 0 , sz (x) )
#define LOCAL
namespace Spinoza{
namespace IO{
#ifndef LOCAL
constexpr auto maxn=1<<20;
char in[maxn],out[maxn],*p1=in,*p2=in,*p3=out;
#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,maxn,stdin),p1==p2)?EOF:*p1++)
#define flush() (fwrite(out,1,p3-out,stdout))
#define putchar(x) (p3==out+maxn&&(flush(),p3=out),*p3++=(x))
class Flush{public:~Flush(){flush();}}_;
#endif
namespace usr{
template<typename type>
inline type read(type &x){
x=0;bool flag(0);char ch=getchar();
while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return flag?x=-x:x;}
template<typename type>
inline void write(type x){
x<0?x=-x,putchar('-'):0;
static short Stack[50],top(0);
do Stack[++top]=x%10,x/=10;while(x);
while(top) putchar(Stack[top--]|48);}
inline char read(char &x){do x=getchar();while(isspace(x));return x;}
inline char write(const char &x){return putchar(x);}
inline void read(char *x){static char ch;read(ch);do *(x++)=ch;while(!isspace(ch=getchar())&&~ch);}
template<typename type>inline void write(type *x){while(*x)putchar(*(x++));}
inline void read(string &x){static char ch;read(ch),x.clear();do x+=ch;while(!isspace(ch=getchar())&&~ch);}
inline void write(const string &x){for(int i=0,len=x.length();i<len;++i)putchar(x[i]);}
template<typename type,typename...T>inline void read(type &x,T&...y){read(x),read(y...);}
template<typename type,typename...T>
inline void write(const type &x,const T&...y){write(x),putchar(' '),write(y...),sizeof...(y)^1?0:putchar('\n');}
template<typename type>
inline void put(const type &x,bool flag=1){write(x),flag?putchar('\n'):putchar(' ');}}
#ifndef LOCAL
#undef getchar
#undef flush
#undef putchar
#endif
}using namespace IO::usr;
}using namespace Spinoza::IO::usr;
template<class T>
constexpr T qpow(T a, ll b) {T res = 1;for (; b; b /= 2, a = a * a %P) {if (b % 2) {res = res * a % P;}}return res;}
template<class T>
constexpr T power(T a, ll b) {T res = 1;for (; b; b /= 2, a *= a) {if (b % 2) {res *= a;}}return res;}
constexpr ll mul(ll a, ll b, ll p) {ll res = a * b - ll(1.L * a * b / p) * p;res %= p;if (res < 0) {res += p;}return res;}
template<ll P>
struct MLong {
ll x;
constexpr MLong() : x{} {}
constexpr MLong(ll x) : x{norm(x % getMod())} {}
static ll Mod;constexpr static ll getMod() {if (P > 0) {return P;} else {return Mod;}}
constexpr static void setMod(ll Mod_) {Mod = Mod_;}
constexpr ll norm(ll x) const {if (x < 0) {x += getMod();}if (x >= getMod()) {x -= getMod();}return x;}
constexpr ll val() const {return x;}
explicit constexpr operator ll() const {return x;}
constexpr MLong operator-() const {MLong res;res.x = norm(getMod() - x);return res;}
constexpr MLong inv() const {assert(x != 0);return power(*this, getMod() - 2);}
constexpr MLong &operator*=(MLong rhs) & {x = mul(x, rhs.x, getMod());return *this;}
constexpr MLong &operator+=(MLong rhs) & {x = norm(x + rhs.x);return *this;}
constexpr MLong &operator-=(MLong rhs) & {x = norm(x - rhs.x);return *this;}
constexpr MLong &operator/=(MLong rhs) & {return *this *= rhs.inv();}
friend constexpr MLong operator*(MLong lhs, MLong rhs) {MLong res = lhs;res *= rhs; return res;}
friend constexpr MLong operator+(MLong lhs, MLong rhs) {MLong res = lhs;res += rhs; return res; }
friend constexpr MLong operator-(MLong lhs, MLong rhs) {MLong res = lhs;res -= rhs; return res; }
friend constexpr MLong operator/(MLong lhs, MLong rhs) {MLong res = lhs;res /= rhs; return res; }
friend constexpr std::istream &operator>>(std::istream &is, MLong &a) {ll v;is >> v;a = MLong(v);return is;}
friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) {return os << a.val();}
friend constexpr bool operator==(MLong lhs, MLong rhs) {return lhs.val() == rhs.val();}
friend constexpr bool operator!=(MLong lhs, MLong rhs) {return lhs.val() != rhs.val();}
constexpr MLong cbrt() const { return pow((P + P - 1) / 3); }
constexpr MLong pow(auto k) const {MLong a = x;MLong b = 1;for (; k; k >>= 1) {if (k & 1)b *= a;a *= a;}return b;}
constexpr MLong sqrt() const {if (pow(P >> 1).x != 1) return 0;MLong a = pow(60);MLong b = pow(119);
for (int k = 21; k >= 0; --k)if (b.pow(1 << k).x != 1) {a *= MLong(3).pow(P >> (k + 2));b *= MLong(3).pow(P >> (k + 1));}
return std::min(a.x, P - a.x);}
};
template<>
ll MLong<0LL>::Mod = ll(1E18) + 9;
template<int P>
struct MInt {
int x;
constexpr MInt() : x{} {}
constexpr MInt(ll x) : x{norm(x % getMod())} {}
static int Mod;
constexpr static int getMod() {if (P > 0) {return P;}else {return Mod;} }
constexpr static void setMod(int Mod_) {Mod = Mod_;}
constexpr int norm(int x) const {if (x < 0) {x += getMod();}if (x >= getMod()) {x -= getMod();}return x;}
constexpr int val() const {return x;}
explicit constexpr operator int() const {return x;}
constexpr MInt operator-() const {MInt res;res.x = norm(getMod() - x);return res;}
constexpr MInt inv() const {assert(x != 0);return power(*this, getMod() - 2);}
constexpr MInt &operator*=(MInt rhs) & {x = 1LL * x * rhs.x % getMod();return *this; }
constexpr MInt &operator+=(MInt rhs) & {x = norm(x + rhs.x);return *this; }
constexpr MInt &operator-=(MInt rhs) & {x = norm(x - rhs.x);return *this;}
constexpr MInt &operator/=(MInt rhs) & {return *this *= rhs.inv();}
friend constexpr MInt operator*(MInt lhs, MInt rhs) {MInt res = lhs;res *= rhs;return res;}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {MInt res = lhs;res += rhs; return res; }
friend constexpr MInt operator-(MInt lhs, MInt rhs) {MInt res = lhs;res -= rhs;return res;}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {MInt res = lhs;res /= rhs;return res;}
friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {ll v;is >> v;a = MInt(v);return is;}
friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {return os << a.val();}
friend constexpr bool operator==(MInt lhs, MInt rhs) {return lhs.val() == rhs.val();}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {return lhs.val() != rhs.val();}
constexpr MInt cbrt() const { return pow((P + P - 1) / 3); }
constexpr MInt pow(auto k) const {MInt a = x;MInt b = 1;for (; k; k >>= 1) {if (k & 1)b *= a;a *= a;}return b;}
constexpr MInt sqrt() const {if (pow(P >> 1).x != 1) return 0;MInt a = pow(60);MInt b = pow(119);
for (int k = 21; k >= 0; --k)if (b.pow(1 << k).x != 1) {a *= MInt(3).pow(P >> (k + 2));b *= MInt(3).pow(P >> (k + 1));}
return std::min(a.x, P - a.x);}
};
template<>
int MInt<0>::Mod = 998244353;
template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();
using modint = MInt<P>;
modint fac[N],inv[N],ivv[N];
void __attribute__((constructor))init(){
fac[0]=fac[1]=1;inv[0]=inv[1]=1;ivv[0]=ivv[1]=1;
for(int i=2;i<N;++i) fac[i]=fac[i-1]*i;
for(int i=2;i<N;++i) inv[i]=inv[P%i]*(P-P/i);
for(int i=2;i<N;++i) ivv[i]=ivv[i-1]*inv[i];
//ivv[N]=MInt(fac[N]).inv();
//for(int i=N-1;i>=0;--i) ivv[i]=ivv[i+1]*(i+1)%P;
}
void solve(){
ll n,a;read(n,a);
vector<ll> sp(n+1);
ll ans=0;
forfront(i,1,n) {read(sp[i]);if (sp[i]) ans+=3;}
priority_queue<ll,vector<ll>,less<ll>> q;
forfront(i,1,n){
ll mount=0;
if (sp[i]==0) mount++;
if ((i==n?sp[1]:sp[i+1]) ==0) mount++;
if ((i==1?sp[n]:sp[i-1]) ==0) mount++;
q.push(mount);
}
a=n-a;
while(a--&&(!q.empty())){
ans+=q.top();
q.pop();
}
write(ans);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout<<fixed<<setprecision(4);
int t=1;
// init();
// cin>>t;
while(t--)
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 19ms
memory: 15788kb
input:
5 2 1 0 1 0 1
output:
13
result:
ok 1 number(s): "13"
Test #2:
score: 0
Accepted
time: 21ms
memory: 17188kb
input:
100000 33292 1 1 1 1 0 1 1 0 0 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 1 1 1 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 1 0 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 1 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 0 0...
output:
279236
result:
ok 1 number(s): "279236"
Test #3:
score: 0
Accepted
time: 18ms
memory: 17196kb
input:
100000 91906 1 1 1 1 1 0 1 0 0 0 1 0 0 0 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 0 1 1 0 0 0 1 0 0 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 1 1 0 0 1 0...
output:
174297
result:
ok 1 number(s): "174297"
Test #4:
score: 0
Accepted
time: 26ms
memory: 17212kb
input:
100000 1825 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 1 1 0 0 0 1 1 1 0 1 1 1 1 0 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 0 0 1 1 1 1 0 1 0 0 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 0 1 1 0 0 1 0 0 1 1 0 0 1 0 1 1 1 ...
output:
300000
result:
ok 1 number(s): "300000"
Test #5:
score: 0
Accepted
time: 16ms
memory: 17168kb
input:
100000 36092 0 0 0 0 1 1 0 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 1 0 1 1 0 0 1 0 1 0 0 0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 0...
output:
276360
result:
ok 1 number(s): "276360"
Test #6:
score: 0
Accepted
time: 17ms
memory: 17192kb
input:
100000 46012 0 0 0 0 1 0 0 0 1 1 0 1 0 1 0 1 1 1 1 1 1 0 0 1 0 1 1 0 1 1 0 1 1 0 1 0 0 1 0 1 0 1 1 1 1 1 0 0 1 0 1 0 1 1 1 0 1 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 1 0 0 0 0 1 1 1 1 0 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 1...
output:
266477
result:
ok 1 number(s): "266477"
Test #7:
score: 0
Accepted
time: 22ms
memory: 17164kb
input:
100000 4625 1 1 1 1 0 1 0 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1 0 0 1 1 ...
output:
300000
result:
ok 1 number(s): "300000"
Test #8:
score: 0
Accepted
time: 26ms
memory: 17220kb
input:
100000 14545 1 1 1 1 1 1 0 1 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 0 1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 1 1 1 0 0 0 1 0 0 1 0 1 1 0 1 1 1 1 0 0...
output:
297977
result:
ok 1 number(s): "297977"
Test #9:
score: 0
Accepted
time: 12ms
memory: 17196kb
input:
100000 24465 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 0 1 0 1 0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 1 0 1 1 1 0 0 1 0 1 0 0 1 1...
output:
287910
result:
ok 1 number(s): "287910"
Test #10:
score: 0
Accepted
time: 17ms
memory: 17212kb
input:
100000 58732 0 0 0 0 1 1 0 0 0 1 1 0 1 1 0 1 0 0 1 0 0 1 0 1 1 0 1 1 0 1 1 1 0 1 0 1 1 1 0 0 0 1 1 0 1 1 0 0 0 1 0 1 0 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 1 0 0 1 1 1 1 1 1 1 0 1 1 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 1...
output:
245071
result:
ok 1 number(s): "245071"
Test #11:
score: 0
Accepted
time: 21ms
memory: 17236kb
input:
100000 22238 1 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 1 1 0 0 1 0 1 0 0 1 1 1 1 0 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 0 1 1 0 0 1 1 1 1 1 1 1 0 1 1 1 0 0 0 1 1 0 1 1 1 1 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 1 1 1 0 1 1 0 1 0 1 1 0 1 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 1 0 1 1 1 0 1 0 0 1...
output:
290348
result:
ok 1 number(s): "290348"
Test #12:
score: 0
Accepted
time: 23ms
memory: 17276kb
input:
100000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
300000
result:
ok 1 number(s): "300000"
Test #13:
score: 0
Accepted
time: 12ms
memory: 17224kb
input:
100000 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
300000
result:
ok 1 number(s): "300000"
Test #14:
score: 0
Accepted
time: 21ms
memory: 17244kb
input:
100000 100000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
0
result:
ok 1 number(s): "0"
Test #15:
score: 0
Accepted
time: 19ms
memory: 17208kb
input:
100000 100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
300000
result:
ok 1 number(s): "300000"